Long long age, there were two people named GTW and DSY, respectively. One day, in order to contend for CZF, the young girl of DSY, they decided to have a duel.
To start with, the two people were given a range, $l,l + 1,l + 2,...,r$, and two numbers, $G$ and $T$. Then, CZF chose either $G$ or $T$ as a number $X$ randomly, and chose an integer $Y$ in the range $[l, r]$ randomly, to perform a special operation, @, which is defined as that X @ Y =((X and Y) or Y) xor X. CZF wanted to know the number of numbers which could be the answer.
Nevertheless, GTW was not able to tackle this problem. In order to win CZF, he asked for your help.
Because the answer can be very large, you only need to print the answer modulo 1000000007.
Input
The first line of the input file contains exactly one integer, $T$, indicating the number of test cases. $(T\leq 10000)$
In the following $T$ lines, each line indicates a test case, containing 4 integers, $l, r, g, t$, whose meanings are given above. ($1\leq l,r,g,t\leq 10^{18},l\leq r$)
Output
There should be $T$ lines in the output file.
In each line of the output file, there should be exactly one number, indicating the answer of the test case respectively.
Sample Input
1
2 4 2 4
Sample Output
4
Hint
2 xor 2=0,2 xor 3=1,2 xor 4=6
4 xor 2=6,4 xor 3=7,4 xor 4=0
There are 4 numbers :0,1,6,7
