You need to count the number of quadruples of integers (X_{1}, X_{2}, X_{3}, X_{4}),
such that L_{i} ≤ X_{i} ≤ R_{i} for i = 1, 2, 3, 4
and X_{1} ≠ X_{2}, X_{2} ≠ X_{3},
X_{3} ≠ X_{4}, X_{4} ≠ X_{1}.

The answer could be quite large.

Hence you should output it modulo (10^{9} + 7).

That is, you need to find the remainder of the answer by (10^{9} + 7).

Input Format

The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.
The only line of each test case contains 8 space-separated integers
L_{1}, R_{1}, L_{2}, R_{2}, L_{3}, R_{3}, L_{4}, R_{4}, in order.

Output Format

For each test case, output a single line containing the number of required quadruples modulo (10^{9} + 7).

Constraints

1 ≤ T ≤ 1000

1 ≤ L_{i} ≤ R_{i} ≤ 10^{9}

Sample Input

5
1 4 1 3 1 2 4 4
1 3 1 2 1 3 3 4
1 3 3 4 2 4 1 4
1 1 2 4 2 3 3 4
3 3 1 2 2 3 1 2

Sample Output

8
10
23
6
5

Explanation

Example case 1. All quadruples in this case are

1 2 1 4
1 3 1 4
1 3 2 4
2 1 2 4
2 3 1 4
2 3 2 4
3 1 2 4
3 2 1 4

Example case 2. All quadruples in this case are

1 2 1 3
1 2 1 4
1 2 3 4
2 1 2 3
2 1 2 4
2 1 3 4
3 1 2 4
3 1 3 4
3 2 1 4
3 2 3 4

Example case 3. All quadruples in this case are

1 3 2 3
1 3 2 4
1 3 4 2
1 3 4 3
1 4 2 3
1 4 2 4
1 4 3 2
1 4 3 4
2 3 2 1
2 3 2 3
2 3 2 4
2 3 4 1
2 3 4 3
2 4 2 1
2 4 2 3
2 4 2 4
2 4 3 1
2 4 3 4
3 4 2 1
3 4 2 4
3 4 3 1
3 4 3 2
3 4 3 4

Example case 4. All quadruples in this case are

1 2 3 4
1 3 2 3
1 3 2 4
1 4 2 3
1 4 2 4
1 4 3 4

Example case 5. All quadruples in this case are

3 1 2 1
3 1 3 1
3 1 3 2
3 2 3 1
3 2 3 2

见题面

见题面