Max Composite N

個のクエリが与えられます。 番目のクエリではが与えられるので、以下で約数を個持つ、最大の整数を出力してください。 ここで、以下では約数個持つ整数が存在することが保証されます。

• 各に対して、以下で約数個持つ整数は存在する

入力はすべて整数である。

Q
X1 k1
X2 K2
  ⋮
xQ kQ

行目に、番目のクエリの結果を出力してください。

5
5 2
36 4
27 3
1356 11
1000000 200

5
35
25
1024
926640