[NOI Online 2022 入门组] 数学游戏

Kri 喜欢玩数字游戏。 一天，他在草稿纸上写下了 $t$ 对正整数 $(x,y)$，并对于每一对正整数计算出了 $z=x\times y\times\gcd(x,y)$。 可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 $y$ 都擦除了，还可能改动了一些 $z$。 现在 Kri 想请你帮忙还原每一组的 $y$，具体地，对于每一组中的 $x$ 和 $z$，你需要输出最小的正整数 $y$，使得 $z=x\times y\times\gcd(x,y)$。如果这样的 $y$ 不存在，也就是 Zay 一定改动了 $z$，那么请输出 $-1$。 注：$\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数，也就是最大的正整数 $d$，满足 $d$ 既是 $x$ 的约数，又是 $y$ 的约数。 ## Input 第一行一个整数 ，表示有 $t$ 对正整数 $x$ 和 $z$。 接下来 $t$ 行，每行两个正整数 $x$ 和 $z$，含义见题目描述。 ## Output 对于每对数字输出一行，如果不存在满足条件的正整数 $y$，请输出 $-1$，否则输出满足条件的最小正整数 $y$。 [samples] ## Background **经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。** 民间数据提供者：@一扶苏一。本题不保证民间数据强度，详见[这个帖子](https://www.luogu.com.cn/discuss/422596)。 ## Note **【样例 1 解释】** $x\times y\times \gcd(x,y)=10\times 12\times\gcd(10,12)=240$。 **【数据范围】** 对于 $20\%$ 的数据，$t, x, z \le {10}^3$。 对于 $40\%$ 的数据，$t \le {10}^3$，$x \le {10}^6$，$z \le {10}^9$。 对于另 $30\%$ 的数据，$t \le {10}^4$。 对于另 $20\%$ 的数据，$x \le {10}^6$。 对于 $100\%$ 的数据，$1 \le t \le 5 \times {10}^5$，$1 \le x \le {10}^9$，$1 \le z < 2^{63}$。