問題文


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

制約


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

入力


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

Q
X1 k1
X2 K2
  ⋮
xQ kQ

出力


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

サンプル


入力1
5
5 2
36 4
27 3
1356 11
1000000 200
出力1
5
35
25
1024
926640

Submit


Go (1.14)