After a long and exhausting semester, Bald decided to take a break and reflect. However, he remembered that he had been studying discrete mathematics throughout the semester. So, he came up with a problem to challenge his professor, Dr. Daoud.
Bald will give Siniora two coprime$$$^\dagger$$$ non-negative integers $$$a$$$ and $$$b$$$. The challenge for Siniora is to find an integer $$$1 \lt c \leq 2^{63} - 1$$$ that is coprime with both $$$a$$$ and $$$b$$$, or report that no such integer exists.
Dr. Daoud thinks this task is so trivial that he won't even bother solving it himself. Instead, he has decided to assign the task to you.
$$$\rule{20em}{0.4pt}$$$
$$$^\dagger$$$ Two non-negative integers are said to be coprime if their greatest common divisor (GCD) is equal to $$$1$$$. For instance, the integers 3 and 10 are coprime since $$$\text{gcd(3, 10) = 1}$$$, while 5 and 10 are not coprime as $$$\text{gcd(5, 10) = 5}$$$.
Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$ — the number of test cases.
The single line of each test case contains two integers $$$a, b$$$ $$$(0 \leq a, b \leq 10^{18})$$$.
It is guaranteed that $$$a$$$ and $$$b$$$ are coprime.
Output any integer $$$1 \lt c \leq 2^{63} - 1$$$ that is coprime with both $$$a$$$ and $$$b$$$. If no such integer exits, output $$$-1$$$.
44 93 1020 2910000000 10000001
5 7 3 3
For the first test case, we have $$$a = 4$$$ and $$$b = 9$$$. So, we output $$$5$$$. It is clear that $$$5$$$ is coprime with both $$$4$$$ and $$$9$$$.
Note that there are other valid values for $$$c$$$, such as $$$7, 11, 19, 25$$$.
