問題文

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

制約

  • 1Q1051 \leq Q \leq 10 ^ 5
  • 2Xi1062 \leq X_i \leq 10 ^ 6
  • iiに対して、XiX_i以下で約数kiをk_i個持つ整数は存在する

入力

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

Q
X1 k1
X2 K2
  ⋮
xQ kQ

出力

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

サンプル

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

Submit


Go (1.21)