Description

Given $l1, r1, l2, r2, l3, r3, l4, r4,$ please count the number of four-tuples $(x1, x2, x3, x4)$ such that $li≤xi≤ri$ and $x1≠x2$, $x2≠x3$, $x3≠x4$,$x4≠x1$. The answer should modulo 1e9+7 before output.

Input

The input consists of several test cases. The first line gives the number of test cases, $T (1≤T≤106)$. For each test case, the input contains one line with 8 integers $l1, r1, l2, r2, l3, r3, l4, r4 (1≤li≤ri≤109)$.

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