Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

There is an infinite plane and we use (x,y) to describe points on the plane. There is a number on every point, represented by p(x,y). And the plane satisfy the following conditions: 1p(x,y) = 0 {x<=0 || y<=0} 2p(1,1) = 1 3p(x,y) = p(x-1,y-1)^p(x,y-2) {(x>0 || y>0) && (x!=1 || y!=1)} PS: ^ represent XOR! Now, give you some points, please output the number on these points.

Input

The first line of the input is the number of cases. (test case <= 10000) Then each case contain two numbers x,y. (-10000<=|x|,|y| <= 10000)

Output

The number on the point (x,y).

Sample Input

10 -1 0 -999 1098 8888 8888 2 6 1 15 9 11 15 16 15 17 524 3468 6568 4818

Sample Output

0 0 1 1 1 1 0 1 1 0

Author

qw4990