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
hide comments
enzymii:
20180205 08:13:40
Is O(T*sqrt(n)) really okay? I have no idea how to make it faster. 

[Rampage] Blue.Mary:
20160316 04:36:54
This problem requires heaviest constantoptimization among all problems I've ever done in recent 3 months. 

Adarsh kumar:
20151229 21:57:49
Something better than O(T*sqrt(n)) is required ?

Added by:  ashish kumar 
Date:  20151227 
Time limit:  1s2.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  own 