#include <bits/stdc++.h>
const int MOD = 1000000007;
const int inv2 = 500000004;
const int inv3 = 333333336;
const int inv4 = 250000002;
const int inv6 = 166666668;
const int inv72 = 13888889;
const int magic3[3] = {0, -32, -16};
const int magic6[6] = {-16, 36, -32, 20, 0, 4};
int _add(int x) { return x < MOD ? x : x - MOD; }
int add(int x, int y) { return _add(x + y); }
int _sub(int x) { return x < 0 ? x + MOD : x; }
int sub(int x, int y) { return _sub(x - y); }
int mul(int x, int y) { return 1LL * x * y % MOD; }
int f4(int x) {
  int res = mul(x + 6, mul(x, x));
  if (x % 2 == 0)
    res = add(res, MOD + magic3[x / 2 % 3]);
  else
    res = add(res, add(mul(9, x), MOD + magic6[(x - 1) / 2 % 6]));
  res = mul(inv72, res);
  return res;
}
int f3(int x, int y) {
  int res = mul(inv6, mul(add(x, y) + 4, mul(x + 1, y + 1)));
  if (x % 3 + y % 3 < 2) res = sub(res, mul(inv3, 2));
  return res;
}
int f2(int x, int y) {
  int res = mul(inv4, mul(y + 1, mul(x, x + 4)));
  if (x % 2 == 1) {
    res = add(res, mul(inv4, y + 1));
    if (y % 2 == 0)
      if (x % 4 == 1)
        res = sub(res, inv2);
      else
        res = add(res, inv2);
  }
  return res;
}
int f(int x, int y) {
  if (x < y) return f(y, x);
  int res = 0;
  if (y < x / 2) {
    res = add(res, f2(x, y));
    x = y * 2;
    res = sub(res, f2(x, y));
  }
  res = add(res, add(f3(x, y), add(f4(x), f4(y))));
  return res;
}
int solve() {
  int x, y, n, m;
  scanf("%d%d%d%d", &x, &y, &n, &m);
  --x;
  --y;
  --n;
  --m;
  --x;
  --y;
  int res = sub(add(f(n, m), f(x, y)), add(f(x, m), f(n, y)));
  if (x == 1 && y == 1) res = add(res, 2);
  return res;
}
int main() {
  int t;
  scanf("%d", &t);
  for (int i = 1; i <= t; ++i) printf("%d\n", solve());
}

### Prompt

Develop a solution in CPP to the problem described below:

Mr. Chanek just won the national chess tournament and got a huge chessboard of size N × M. Bored with playing conventional chess, Mr. Chanek now defines a function F(X, Y), which denotes the minimum number of moves to move a knight from square (1, 1) to square (X, Y). It turns out finding F(X, Y) is too simple, so Mr. Chanek defines:

G(X, Y) = ∑_{i=X}^{N} ∑_{j=Y}^{M} F(i, j)

Given X and Y, you are tasked to find G(X, Y).

A knight can move from square (a, b) to square (a', b') if and only if |a - a'| > 0, |b - b'| > 0, and |a - a'| + |b - b'| = 3. Of course, the knight cannot leave the chessboard.

Input

The first line contains an integer T (1 ≤ T ≤ 100), the number of test cases.

Each test case contains a line with four integers X Y N M (3 ≤ X ≤ N ≤ 10^9, 3 ≤ Y ≤ M ≤ 10^9).

Output

For each test case, print a line with the value of G(X, Y) modulo 10^9 + 7.

Example

Input


2
3 4 5 6
5 5 8 8


Output


27
70

### Response

```cpp
#include <bits/stdc++.h>
const int MOD = 1000000007;
const int inv2 = 500000004;
const int inv3 = 333333336;
const int inv4 = 250000002;
const int inv6 = 166666668;
const int inv72 = 13888889;
const int magic3[3] = {0, -32, -16};
const int magic6[6] = {-16, 36, -32, 20, 0, 4};
int _add(int x) { return x < MOD ? x : x - MOD; }
int add(int x, int y) { return _add(x + y); }
int _sub(int x) { return x < 0 ? x + MOD : x; }
int sub(int x, int y) { return _sub(x - y); }
int mul(int x, int y) { return 1LL * x * y % MOD; }
int f4(int x) {
  int res = mul(x + 6, mul(x, x));
  if (x % 2 == 0)
    res = add(res, MOD + magic3[x / 2 % 3]);
  else
    res = add(res, add(mul(9, x), MOD + magic6[(x - 1) / 2 % 6]));
  res = mul(inv72, res);
  return res;
}
int f3(int x, int y) {
  int res = mul(inv6, mul(add(x, y) + 4, mul(x + 1, y + 1)));
  if (x % 3 + y % 3 < 2) res = sub(res, mul(inv3, 2));
  return res;
}
int f2(int x, int y) {
  int res = mul(inv4, mul(y + 1, mul(x, x + 4)));
  if (x % 2 == 1) {
    res = add(res, mul(inv4, y + 1));
    if (y % 2 == 0)
      if (x % 4 == 1)
        res = sub(res, inv2);
      else
        res = add(res, inv2);
  }
  return res;
}
int f(int x, int y) {
  if (x < y) return f(y, x);
  int res = 0;
  if (y < x / 2) {
    res = add(res, f2(x, y));
    x = y * 2;
    res = sub(res, f2(x, y));
  }
  res = add(res, add(f3(x, y), add(f4(x), f4(y))));
  return res;
}
int solve() {
  int x, y, n, m;
  scanf("%d%d%d%d", &x, &y, &n, &m);
  --x;
  --y;
  --n;
  --m;
  --x;
  --y;
  int res = sub(add(f(n, m), f(x, y)), add(f(x, m), f(n, y)));
  if (x == 1 && y == 1) res = add(res, 2);
  return res;
}
int main() {
  int t;
  scanf("%d", &t);
  for (int i = 1; i <= t; ++i) printf("%d\n", solve());
}

```