Problem Description

You are given $4$ positive integers $x_1, x_2, y_1, y_2$. Now you need to calculate $$\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} \left( \left\lfloor \frac{i}{x_1} \right\rfloor + \left\lfloor \frac{x_2}{i} \right\rfloor + \left\lfloor \frac{j}{y_1} \right\rfloor + \left\lfloor \frac{y_2}{j} \right\rfloor \right)^2$$ where $\lfloor x \rfloor$ denotes the biggest integer that is not bigger than $x$.

The answer may be too large, so you just need to output it modulo $(10^9+7)$.

Input

The first line of input contains an integer $T$ ($1\leq T \leq 100$), denoting the number of test cases.

Each test case contains $4$ positive integers $x_1, x_2, y_1, y_2$ in one line. $1\leq x_1 \leq x_2 \leq 10^9$. $1\leq y_1 \leq y_2 \leq 10^9$.

Output

For each test case, print one integer in one line, denoting your answer modulo $(10^9+7)$.

5
1 1 1 1
1 2 3 4
2 5 2 5
1 12345678 2 23456789
3 123456789 4 1000000000

16
100
490
841328555
80052041