E. Army Value
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Age of Empires is a fun game that has 3 types of army (archers, melee, cavalry), each of which can have an army value between $$$[l_i, r_i]$$$.

Ahmad is playing a game that he wants to win, and to do so he should select the armies value such that $$$(a_1 \oplus a_2 \oplus a_3)$$$ has a prime number of ones in its binary representation, here $$$a_i$$$ is the value of the army with the $$$i$$$-th type, and $$$\oplus$$$ is the Exclusive OR.

Since Ahmad is busy playing the game, he needs you to calculate the number of ways he could choose the army values such that he can win modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 100)$$$ – the number of test cases.

Then for each test case there are three lines each containing the $$$i$$$-th interval $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq l_i \leq r_i \leq 10^9)$$$ – the possible values for the $$$i$$$-th army type.

Output

For each test case print one integer, the answer to the test case modulo $$$(10^9 + 7)$$$.

Examples
Input
1
1 3
1 3
2 3
Output
5
Input
4
1 10
2 4
1 6
1 4
3 6
4 10
1 3
1 3
1 3
1 1
1 1
1 1
Output
101
62
7
0
Note

In the first example, these are the $$$5$$$ ways to choose the armies value:

  • $$$(1, 1, 3)$$$;
  • $$$(2, 2, 3)$$$;
  • $$$(2, 3, 2)$$$;
  • $$$(3, 2, 2)$$$;
  • $$$(3, 3, 3)$$$.

and all their XOR have the same binary representation $$$011$$$ which has $$$2$$$ ones, and $$$2$$$ is a prime.