题目描述
Problem Description
Kri loves playing with numbers.
One day, he wrote down \( t \) pairs of positive integers \((x, y)\) on a draft paper and calculated \( z = x \times y \times \gcd(x, y) \) for each pair.
However, mischievous Zay found Kri's draft paper and erased all the \( y \) values, and possibly altered some \( z \) values.
Now, Kri wants you to help restore each \( y \). Specifically, for each pair of \( 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 altered \( z \), then output \(-1\).
Note: \(\gcd(x, y)\) denotes the greatest common divisor of \( x \) and \( y \), which is the largest positive integer \( d \) that divides both \( x \) and \( y \).
Input Format
The first line contains an integer \( t \), indicating the number of pairs of positive integers \( x \) and \( z \).
The next \( t \) lines each contain two positive integers \( x \) and \( z \), as described in the problem statement.
Output Format
For each pair of numbers, output one line. If no such positive integer \( y \) exists, output \(-1\); otherwise, output the smallest positive integer \( y \) that satisfies the condition.
Sample Input and Output
Sample Input #1
1
10 240
Sample Output #1
12
Sample Input #2
3
5 30
4 8
11 11
Sample Output #2
6
-1
1
Sample Input #3
See attached file math3.in
Sample Output #3
See attached file math3.out
Sample Input #4
See attached file math4.in
Sample Output #4
See attached file math4.out
Notes
[Sample 1 Explanation]
\( x \times y \times \gcd(x, y) = 10 \times 12 \times \gcd(10, 12) = 240 \).
[Data Range]
For 20% of the data, \( t, x, z \leq 10^3 \).
For 40% of the data, \( t \leq 10^3 \), \( x \leq 10^6 \), \( z \leq 10^9 \).
For another 30% of the data, \( t \leq 10^4 \).
For another 20% of the data, \( x \leq 10^6 \).
For 100% of the data, \( 1 \leq t \leq 5 \times 10^5 \), \( 1 \leq x \leq 10^9 \), \( 1 \leq z < 2^{63} \).
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分