Four-tuples

Time Limit: 2000 ms Memory Limit: 524288 KiB

Problem Description

Given $l_{1}$, $r_{1}$, $l_{2}$, $r_{2}$, $l_{3}$, $r_{3}$, $l_{4}$, $r_{4}$, please count the number of four-tuples ($x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$) such that $l_{i} \leq x_{i} \leq r_{i}$ and $x_{1} \ne x_{2}$, $x_{2} \ne x_{3}$, $x_{3} \ne x_{4}$, $x_{4} \ne x_{1}$. The answer should modulo $10^{9} + 7$ before output.

Input

The input consists of several test cases. The first line gives the number of test cases, $T$ ($1 \leq T \leq 10^{6}$).
For each test case, the input contains one line with 8 integers $l_{1}$, $r_{1}$, $l_{2}$, $r_{2}$, $l_{3}$, $r_{3}$, $l_{4}$, $r_{4}$ ($1 \leq l_{i} \leq r_{i} \leq 10^{9}$).

Output

For each test case, output one line containing one integer, representing the answer.

Sample Input

1
1 1 2 2 3 3 4 4

Sample Output

1

Hint

赛时真题重现

Source

2018 Shandong ACM programing real contest, on-site problem replay with the powerful judger