## GCDMAT2 - GCD OF MATRIX (hard)

You have given a matrix of size nxm. Every cell of matrix denote gcd of respective indices. For ex-

A 3x2 matrix have entries

 gcd(1,1) gcd(1,2) gcd(2,1) gcd(2,2) gcd(3,1) gcd(3,2)

You have given queries i1 j1 i2 j2.

You have to find the sum of matrix formed by upper left corner (i1,j1) and lower right corner (i2,j2).

### Input

First line indicates number of testcases. (T<=50000)

Next line have space separated two integer n and m. (1<=n,m<=1000000).

Next T lines contains queries i1 j1 i2 j2.

where i1<=i2 j1<=j2.

### Output

Print ans modulo M for each query in newline. (M=10^9+7)

### Example

```Input:
2
3 2
1 1 2 2
2 1 3 2

Output:
5
5``` enzymii: 2018-02-05 08:13:40 Is O(T*sqrt(n)) really okay? I have no idea how to make it faster. [Rampage] Blue.Mary: 2016-03-16 04:36:54 This problem requires heaviest constant-optimization among all problems I've ever done in recent 3 months. Adarsh kumar: 2015-12-29 21:57:49 Something better than O(T*sqrt(n)) is required ? ->use some opimisation Last edit: 2015-12-31 07:48:04