C. gcd
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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) \gt 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

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line of each test case contains two positive integers $$$a,b$$$ ($$$1 \leq a,b \leq 10^{18}$$$).

Output

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.
Example
Input
5
1 2
2 1
3 6
1000000000000000000 1000000000000000000
172635817456 237896190123
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.