Background

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.

Problem Description

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$.

Input Format

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.

Output Format

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.

1
10 240

12

3
5 30
4 8
11 11

6
-1
1

见附件中的 math3.in

见附件中的 math3.out

见附件中的 math4.in

见附件中的 math4.out

Hint

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