Xor Grid

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Recently Chef invented a new structure that he has called Xor Grid. It is an infinitely large grid G filled with numbers based on these three rules:
 G[1, c] = 1 for all c ≥ 1
 G[r, 1] = r for all r ≥ 1
 G[r, c] = G[r  1, c] xor G[r, c  1] for all r > 1 and c > 1
Now Chef is wondering, what are the xor sums of all the numbers within some specific rectangles of the Xor Grid?
Note
Xor sum refers to successive xor operations on integers. For example, xor sum of integers x_{1}, x_{2}, x_{3}, ..., x_{n} will be (..((x_{1} xor x_{2}) xor x_{3})... xor x_{n}).Input
The first line of the input contains an integer T denoting the number of test cases.
For each test case, the only line of input contains four integers r1, r2, c1 and c2, where (r1, c1), (r2, c2) denotes the coordinates of top left and bottom right cells of the rectangle.
Output
For each test case, output a single integer ― the xor sum of all the numbers within G[r1..r2, c1..c2].Constraints
 1 ≤ T ≤ 10 000
 1 ≤ r1 ≤ r2 ≤ 10^{18}
 1 ≤ c1 ≤ c2 ≤ 10^{18}
Example
Input: 5 1 1 71 93 23959042 23959042 1 1 1 2 1 2 2 7 3 6 5 8 5 8 Output: 1 23959042 1 6 4
Explanation
Example case 1. First row is filled with ones, so our rectangle contains 23 ones and their xor sum is one. Example case 2. Here we have a rectangle that consists of one cell G[23959042, 1] = 23959042. Example case 3. The rectangle contains four numbers: 1 1 2 3 and their xor sum is 1.Author:  alex_2oo8 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/XRGRD 
Tags  alex_2oo8, bitwiseoperatn, cook78, easymedium, fractals, maths 
Date Added:  8082016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 