Description

The previous problem is from 2018 Shandong ACM programing contest。 But lmh find this problem have problem, it's test data is different from he did on the day of this contest. So after his hard work, he find the real data and find a powerful judger used to this problem. Now he succeeded in replaying the difficulty of that time. Can you solve it? 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