Fakültələr dərəcələr verir#6543
Fred Fakulti və Pol Pauer böyük ədədlərə maraq göstərirlər. Hər gün Fred təsadüfi bir tam ədəd seçir və hesablayır. Onun dostu Pol isə təsadüfi seçilmiş tam ədəd -nin müxtəlif qüvvətlərini, məsələn k^2, k^3 və s. hesablayaraq əylənir. İsti yay günlərinin birində Fred və Pol çox darıxdılar və dostları Deyv Divayderə zarafat etmək qərarına gəldilər. Fred təsadüfi bir tam ədəd seçir, Pol isə təsadüfi bir tam ədəd seçir. Onlar istəyirlər ki, Deyv elə ən böyük tam ədəd tapsın ki, k^i -i qalıqsız bölə bilsin, əks halda onlar Deyvə tort atacaqlar.
Deyv üzünə tort atılmasını sevmədiyi üçün, sizdən ona belə bir tam ədəd tapmaqda kömək etməyinizi istəyir.
Birinci sətir testlərin sayı t~(1 \le t \le 100)-ü ehtiva edir. Növbəti sətirin hər biri iki ədəd və k~(2 \le n \le 10^{18}, 2 \le k \le 10^{12})-ni ehtiva edir.
Hər bir test üçün maksimum tam ədəd -ni ayrı sətirdə çıxarın.
Nümunə 1