Operation bits - A new operation conducted by the secret team currently working on a project on security enhancement. Mr. Abay, the team head, has found a new pattern on the perfect squares. This can be used as a outer cover for his project as its securing power is low. So he assign you this problem to find the key based on the given conditions:

"An two adjacent perfect squares have their absolute difference as an odd number except when a and b are equal. Your task is to find the key which is defined as: 

key(a, b) where a and b are perfect squares is ( ( AND( absolute difference between every adjacent perfect squares in [a, b]) ) AND ( XOR( absolute difference between every adjacent perfect squares in [a, b]) ) )"

Find the key for the given inputs :)

Input

The input begins with a number T (1 ≤ T ≤ 1000) where T is the number of test cases.

T lines follow

Each line has two numbers a and b (0 < a ≤ b ≤ 10⁶)

It is assured that a and b are perfect squares.

Output

For each test case print the corresponding key.

Example

Input:
2
1 4
25 49

Output:
3
0

for test case 1 we have key=(3)&(3)=3