GCD Plus LCM

In this problem you will be given two integers $a$, $b$. You have to answer if $GCD(a, b) + LCM(a, b) = a+b$ is true or not.

Input

Input begins with an integer $T$ ($0 < T ≤ 10^6$) for the number of cases to follow. Next T lines each contain two integers $a$ and $b$ ($0 < a, b ≤ 10^{18}$).

Output

For each case print $\texttt{true}$ or $\texttt{false}$ without quotes according to the problem statement.

Sample

Input	Output
3 2 10 2 3 4 6	true false false