Description

Given positive integers $a, b$. Find a positive integer $x$ such that:

• $1 \leq x \leq 10^{18}$.

• $\gcd(a, x) = 1$ and $\gcd(b, x) > 1$.

If it is impossible to find such an integer $x$, output $-1$.

Here $\gcd(a, b)$ denotes the greatest common divisor of $a$ and $b$, which is the maximum positive integer that divides both $a$ and $b$.

Input Format

Each test contains multiple test cases. The first line contains the number of test cases $T$ .

The description of the test cases follows.

The first line of each test case contains two positive integers $a, b$ .

$1 \leq T \leq 10^4,1 \leq a, b \leq 10^{18}$

Output Format

For each test case:

• If such an integer $x$ doesn't exist, output a single integer $-1$.

• Otherwise, output the integer $x$. If there are multiple answers, output any of them.

Sample Input

5
1 2
2 1
3 6
1000000000000000000 1000000000000000000
172635817456 237896190123

Sample Output

2
-1
2
-1
237896190123

Note

In the first test case, $a = 1$, $b = 2$, let $x = 2$, then $gcd(a, x) = gcd(1, 2) = 1$, $gcd(b, x) = gcd(2, 2) = 2$, which satisfies the condition.

In the second test case, it can be proved that no such $x$ exists.

In the third test case, $a = 3$, $b = 6$, let $x = 2$, then $gcd(a, x) = gcd(3, 2) = 1$, $gcd(b, x) = gcd(6, 2) = 2$, which satisfies the condition.