GCDMAT - GCD OF MATRIX

### 题目描述 给定 $n, m$，再在每组数据中给定不大于 $n$ 的整数 $i_1, j_1$ 和不大于 $m$ 的整数 $i_2, j_2$，求出 $\displaystyle\sum_{i = i_1}^{i_2} \sum_{j = j_1}^{j_2} \gcd(i, j)$ 的值。 由于结果可能很大，所以你只需要求出结果对 $10^9 + 7$ 取模的值。 ### 输入格式 **本题有多组测试数据。** 第一行，一个整数 $T$，表示数据组数； 第二行，两个整数 $n, m$。 对于每组数据： 一行，四个整数 $i_1, j_1, i_2, j_2$。 ### 输出格式 对于每组数据，输出一行，一个整数，表示所求的值。 ### 说明/提示 对于 $100\%$ 的数据， $1 \leq n, m \leq 5 \times 10^4$， $1 \leq i_1, j_1 \leq n$， $1 \leq i_2, j_2 \leq m$， $1 \leq T \leq 500$。

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<=500) Next line have space separated two integer n and m. (1<=n,m<=50000). 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