Restore Y from X and Z

Kri enjoys playing with numbers. One day, he wrote down t pairs of positive integers \((x, y)\) and computed \(z = x \times y \times \gcd(x, y)\) for each pair. However, mischievous Zay erased the value of \(y\) in every pair and may have even modified the value of \(z\).

Your task is: for every pair of given \(x\) and \(z\), find the smallest positive integer \(y\) such that \[ z = x \times y \times \gcd(x,y). \] If no such \(y\) exists (which implies that Zay definitely tampered with \(z\)), output -1.

Note: \(\gcd(x,y)\) denotes the greatest common divisor of \(x\) and \(y\), i.e. the largest positive integer that divides both \(x\) and \(y\).

inputFormat

The first line contains a single integer \(T\) (\(1 \le T\)) representing the number of test cases. Each of the next \(T\) lines contains two positive integers \(x\) and \(z\) separated by a space.

outputFormat

For each test case, output a single line containing the smallest positive integer \(y\) that satisfies the equation \(z = x \times y \times \gcd(x,y)\). If no such \(y\) exists, output -1.

sample

4
10 120
20 500
5 14
4 4

6
5
-1
1