Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

GCD Plus LCM

Limits 1s, 512 MB

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 ≤ 106) for the number of cases to follow. Next T lines each contain two integers a and b (0 < a, b ≤ 1018).

Output

For each case print “true” or “false” without quotes according to the problem statement.

Samples

InputOutput
3
2 10
2 3
4 6
true
false
false

Discussion
Submit

Login to submit