QQQ個のクエリが与えられます。 iii番目のクエリではXi,kiX_i, k_iXi,kiが与えられるので、XiX_iXi以下で約数をkik_iki個持つ、最大の整数を出力してください。\\ ここで、XiX_iXi以下では約数をkiをk_iをki個持つ整数が存在することが保証されます。
入力はすべて整数である。
Q X1 k1 X2 K2 ⋮ xQ kQ
iii行目に、iii番目のクエリの結果を出力してください。
5 5 2 36 4 27 3 1356 11 1000000 200
5 35 25 1024 926640