### 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.

1
1 1 2 2 3 3 4 4

1

#### Source

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