P8255 [NOI Online 2022 Junior] Math Game

**After consideration by the administrators, we plan to store the community testdata separately in the last Subtask. These test points are all worth 0 points, but failing any of them will be considered as not passing this problem.** Community testdata provider: @一扶苏一. This problem does not guarantee the strength of the community testdata. For details, see [this post](https://www.luogu.com.cn/discuss/422596).

Kri likes playing number games. One day, he wrote down $t$ pairs of positive integers $(x, y)$ on scratch paper, and for each pair computed $z = x \times y \times \gcd(x, y)$. But the naughty Zay found Kri's paper, erased every $y$, and may have modified some $z$ as well. Now Kri asks you to help restore each $y$. Specifically, for each given $x$ and $z$, you need to output the smallest positive integer $y$ such that $z = x \times y \times \gcd(x, y)$. If such a $y$ does not exist, meaning Zay must have modified $z$, output $-1$. Note: $\gcd(x, y)$ denotes the greatest common divisor of $x$ and $y$, i.e. the largest positive integer $d$ such that $d$ is a divisor of both $x$ and $y$.

The first line contains one integer $t$, representing that there are $t$ pairs of positive integers $x$ and $z$. The next $t$ lines each contain two positive integers $x$ and $z$, as described above.

For each pair, output one line. If there is no positive integer $y$ satisfying the condition, output $-1$. Otherwise, output the smallest positive integer $y$ that satisfies the condition.

**Sample 1 Explanation** $x \times y \times \gcd(x, y) = 10 \times 12 \times \gcd(10, 12) = 240$. **Constraints** For $20\%$ of the testdata, $t, x, z \le 10^3$. For $40\%$ of the testdata, $t \le 10^3$, $x \le 10^6$, $z \le 10^9$. For another $30\%$ of the testdata, $t \le 10^4$. For another $20\%$ of the testdata, $x \le 10^6$. For $100\%$ of the testdata, $1 \le t \le 5 \times 10^5$, $1 \le x \le 10^9$, $1 \le z < 2^{63}$. Translated by ChatGPT 5