GCDMAT - GCD OF MATRIX

You have given a matrix of size n×m. Every cell of matrix denote gcd of respective indices. For example

A 3×2 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 test cases. (T<=500)

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

Next T lines contains queries i1 j1 i2 j2. 

where i1<=i2, j1<=j2.

Output

Print answer modulo M for each query in new line. (M=10^9+7)

Example

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

Output:
5
5

Added by:ashish kumar
Date:2015-12-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:own

hide comments
2016-01-02 02:44:29 varun bumb
What does matrix formed by upper left corner (i1,j1) and lower right corner (i2,j2) means?

->i.e matrix be like
(i1,j1) (i1,j1+1) (i1,j1+2) ..... (i1,j2)
(i1+1,j1) ......... (i1+1,j2)
.
.
(i2,j1) (i2,j1+1) (i2,j2)


Last edit: 2016-01-02 17:54:08
2015-12-29 20:15:08 Shambhavi Mishra
Does testcase 8 involves any corner cases ? If so, can you help ?
2015-12-25 14:01:24 abdou_93
i think it the same problem http://www.spoj.com/problems/GCDEX/

-> no its not, you can try to solve this then decide.

Last edit: 2015-12-25 18:50:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.