You need to count the number of quadruples of integers (X₁, X₂, X₃, X₄), such that L_i ≤ X_i ≤ R_i for i = 1, 2, 3, 4 and X₁ ≠ X₂, X₂ ≠ X₃, X₃ ≠ X₄, X₄ ≠ X₁.

The answer could be quite large.
Hence you should output it modulo (10⁹ + 7).
That is, you need to find the remainder of the answer by (10⁹ + 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₁, R₁, L₂, R₂, L₃, R₃, L₄, R₄, in order.

Output Format
For each test case, output a single line containing the number of required quadruples modulo (10⁹ + 7).

Constraints
1 ≤ T ≤ 1000
1 ≤ L_i ≤ R_i ≤ 10⁹

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