SPOJ Brasil

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

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 ≤ 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 answer modulo M for each query in newline. (M = 10⁹+7)

Example

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

Output:
5
5