Four-tuples

Time Limit: 2000 ms Memory Limit: 65536 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\le x_i\le 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\le T\le 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\le l_i\le r_i\le 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

此题数据已确保完整。

如需再次体验赛时刺激的评测环境,请前往 Problem 4206,我们已临时部署了同配置的评测机(经过调优,实测运算速度可达 1e40±4 次/秒)。

Source

“浪潮杯”山东省第九届ACM大学生程序设计竞赛(感谢山东财经大学)