GCDMAT2 - GCD OF MATRIX (hard)

### 题意 求 $$\sum_{i=i1}^{i2}\sum_{j=j1}^{j2}\gcd(i,j)$$ 对$10^9+7$取余,$T$组数据。 ### 输入格式： 第一行$T$表示数据组数，第二行两个整数$n,m$表示$N,M$的最大值，接下来每行四个整数$i1,j1,i2,j2$ ### 数据范围： $T\le50000,N,M\le1000000$

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).

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.

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

2
3 2
1 1 2 2
2 1 3 2

5
5