Kri 喜欢玩数字游戏。
一天，他在草稿纸上写下了 t 对正整数 (x,y)，并对于每一对正整数计算出了 z=x*y*gcd(x,y)。
可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 y 都擦除了，还可能改动了一些 z。
现在 Kri 想请你帮忙还原每一组的 y，具体地，对于每一组中的 x 和 z，你需要输出最小的正整数 y，使得 z=x*y*gcd(x,y)。如果这样的 y 不存在，也就是 Zay 一定改动了 z，那么请输出 -1。
注：gcd(x,y) 表示 x 和 y 的最大公约数，也就是最大的正整数 d，满足 d 既是 x 的约数，又是 y 的约数。

第一行一个整数 ，表示有 t 对正整数 x 和 z。
接下来 t 行，每行两个正整数 x 和 z，含义见题目描述。

对于每对数字输出一行，如果不存在满足条件的正整数 y，请输出 -1，否则输出满足条件的最小正整数 y。

【样例 1 解释】
x*y*gcd(x,y)=10*12*gcd(10,12)=240。




样例二：
输入：
3
5 30
4 8
11 11
输出：
6
-1
1
math



【数据范围】
对于 20% 的数据，t,x,z≤10³。
对于 40% 的数据，t≤10³，x≤10⁶，z≤10⁹。
对于另 30% 的数据，t≤10⁴。
对于另 20% 的数据，x≤10⁶。
对于 100% 的数据，1≤t≤5×10⁵，1≤x≤10⁹，1≤z<2⁶³。

NOIONLINE 2022 普及组 第二题