Addition is written using the plus sign "+" between the terms; that is, in infix notation. The result is expressed with an equals sign. For example:
1 + 1 = 2 (verbally, "one plus one equals two")
2 + 2 = 4 (verbally, "two plus two equals four")
A bitwise exclusive or takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if the two bits are different, and 0 if they are the same. For example:
0101
XOR 0011
= 0110
In the C programming language family, the bitwise XOR operator is "^" (caret).
Now Mr. Y has two numbers P and Q, P = A + B and Q = A ^ B. Then Mr. Y asks you that how many combinations of nonnegative numbers (A, B). Notice that the combinations like (3, 2) and (2, 3) count as the same combination.
Input
In the first line, there is a single integer number T which means T test cases followed.
In the next T lines, every line contains a test case: two integers P and Q. You can assume that 0 <= p, q <= 1,000,000,000.
Output
For each test case, please output a single line with the number of the combinations.