#include <bits/stdc++.h>
template <class c>
int popc(c a) {
  if (sizeof(c) == 8)
    return __builtin_popcountll(a);
  else
    return __builtin_popcount(a);
}
template <class c>
int ctz(c a) {
  if (sizeof(c) == 8)
    return __builtin_ctzll(a);
  else
    return __builtin_ctz(a);
}
template <class c>
int clz(c a) {
  if (sizeof(c) == 8)
    return __builtin_clzll(a);
  else
    return __builtin_clz(a);
}
inline int min(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ first;
}
inline int max(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ second;
}
inline long long min(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ first;
}
inline long long max(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ second;
}
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace escape__from__random__aetuhoetnuhshe {
using namespace std::chrono;
mt19937 rng(duration_cast<milliseconds>(system_clock::now().time_since_epoch())
                .count());
uniform_real_distribution<> prob_dist(0.0, 1.0);
};  // namespace escape__from__random__aetuhoetnuhshe
namespace typedefs {}
namespace numbers_operation {
template <class T>
inline T floor_mod(T a, const T &b) {
  a %= b;
  if (a < 0) a += b;
  return a;
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
using namespace escape__from__random__aetuhoetnuhshe;
const long long MOD = 1e9 + 7;
long long mul(long long a, long long b) { return (1LL * a * b) % MOD; }
long long diff(long long a, long long b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
  return a;
}
void subt(long long &a, const long long &b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
}
long long sum(long long a, long long b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
  return a;
}
void add(long long &a, const long long &b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
}
long long power(long long a, long long deg) {
  long long res = 1;
  for (; deg; a = mul(a, a), deg >>= 1) {
    if (deg & 1) {
      res = mul(res, a);
    }
  }
  return res;
}
long long inverse(long long a) { return power(a, MOD - 2); }
long long _2 = inverse(2);
long long _6 = inverse(6);
long long divide(long long a, long long b) { return mul(a, inverse(b)); }
long long prog2(long long first) { return mul(mul(first, diff(first, 1)), _2); }
long long prog3(long long first) {
  return mul(mul(mul(first, diff(first, 1)), diff(mul(first, 2), 1)), _6);
}
long long magic_aux(long long sumL, long long sumR, long long sumStep,
                    long long cntL, long long cntStep) {
  if (sumR < sumL) {
    return 0;
  }
  long long stepCount = (sumR - sumL) / sumStep + 1;
  long long modSum = 0;
  add(modSum, mul(stepCount, cntL));
  add(modSum, mul(prog2(stepCount), cntStep));
  modSum = mul(modSum, sumL % 3);
  long long funcL = sumL / 3, funcStep = sumStep / 3;
  long long coeff0 = mul(cntL, funcL);
  long long coeff1 = sum(mul(cntL, funcStep), mul(funcL, cntStep));
  long long coeff2 = mul(cntStep, funcStep);
  long long divSum = 0;
  add(divSum, mul(coeff0, stepCount));
  add(divSum, mul(coeff1, prog2(stepCount)));
  add(divSum, mul(coeff2, prog3(stepCount)));
  long long res = sum(modSum, divSum);
  return res;
}
long long magic(long long sumL, long long sumR, long long sumStep,
                long long cntL, long long cntStep) {
  long long res = 0;
  for (long long it = 0; it < 3; ++it) {
    add(res, magic_aux(sumL + it * sumStep, sumR, 3 * sumStep,
                       cntL + cntStep * it, cntStep * 3));
  }
  return res;
}
long long seg2_aux(long long l, long long r) {
  if (l > r) {
    return 0;
  }
  long long r1 = l + 2 * (r - l) / 2;
  long long segCount = (r - l) / 2 + 1;
  long long res = magic(l, r1, 2, segCount, -1);
  return res;
}
long long seg2(long long l, long long r) {
  if (l > r) {
    return 0;
  }
  long long preRes = sum(seg2_aux(l, r), seg2_aux(l + 1, r));
  long long segLen = r - l + 1;
  long long segCount = (r - l) / 2 + 1;
  add(preRes, mul(segLen, prog2(segCount)));
  add(preRes, mul(MOD - 2, prog3(segCount)));
  return preRes;
}
long long calcSmallRect(long long first, long long second) {
  if (first < second) {
    swap(first, second);
  }
  long long rect1 = magic(0, second - 2, 1, 1, 1);
  long long rect2 = magic(second - 1, first - 1, 1, second, 0);
  long long rect3 = magic(first, first + second - 2, 1, second - 1, -1);
  long long right = seg2(1, second - 1);
  long long down = diff(seg2(1, first - 1),
                        seg2(2 * second + 1 + second, first - 1 + second));
  long long res = 0;
  add(res, rect1);
  add(res, rect2);
  add(res, rect3);
  subt(res, right);
  subt(res, down);
  return res;
}
long long f(long long first) { return first / 3 + first % 3; }
long long calcSmallRectStupid(long long first, long long second) {
  long long res = 0;
  for (long long i = 0; i < first; ++i) {
    for (long long j = 0; j < second; ++j) {
      if (2 * i >= j && 2 * j >= i) {
        res += f(i + j);
      }
    }
  }
  return res;
}
long long solveSmallSlow(long long n, long long m) {
  long long rez = 0;
  for (long long first = 0; first < n; first++) {
    for (long long second = 0; second < m; second++) {
      if (first <= 2 * second && second <= 2 * first) {
        if (first <= 2 * second && second <= 2 * first) {
          rez += (first + second) / 3;
          if ((first + second) % 3 == 1) {
            rez += 1;
          }
          if ((first + second) % 3 == 2) {
            rez += 2;
          }
        }
      }
    }
  }
  return rez;
}
template <long long MOD>
struct Ring {
  long long value = 0;
  Ring() {}
  Ring(long long _value) {
    value = _value;
    value = floor_mod(value, MOD);
  }
  Ring pow(long long p) const {
    Ring r = 1;
    Ring first;
    first.value = value;
    while (p) {
      if (p & 1) r *= first;
      first *= first;
      p /= 2;
    }
    return r;
  }
  Ring inv() const { return pow(MOD - 2); }
  void operator*=(const Ring<MOD> &b) {
    value *= b.value;
    value = floor_mod(value, MOD);
  }
  friend Ring operator*(Ring<MOD> a, const Ring<MOD> &b) {
    a *= b;
    return a;
  }
  void operator+=(const Ring<MOD> &b) {
    value += b.value;
    value -= (value >= MOD) * MOD;
  }
  friend Ring operator+(Ring a, const Ring &b) {
    a += b;
    return a;
  }
  void operator-=(const Ring<MOD> &b) {
    value -= b.value;
    value += (value < 0) ? MOD : 0;
  }
  friend Ring operator-(Ring a, const Ring &b) {
    a -= b;
    return a;
  }
  void operator/=(const Ring<MOD> &b) { (*this) *= b.inv(); }
  friend Ring operator/(Ring a, const Ring &b) {
    a /= b;
    return a;
  }
  bool operator==(const Ring<MOD> &b) { return value == b.value; }
  bool operator!=(const Ring<MOD> &b) { return value != b.value; }
  friend void fast_print(const Ring<MOD> &b) { fast_print(b.value); }
};
long long solve(long long n, long long a, long long b, long long m) {
  if (b == 0) return n * (a / m);
  if (a >= m) return n * (a / m) + solve(n, a % m, b, m);
  if (b >= m) return n * (n - 1) / 2 * (b / m) + solve(n, a, b % m, m);
  return solve((a + b * n) / m, (a + b * n) % m, m, b);
}
vector<pair<long long, long long>> shs;
Ring<MOD> solveBigFast(long long n, long long m, long long first) {
  Ring<MOD> rez = 0;
  long long up = min(m, (first + 1) / 2);
  rez += up * (first / 2);
  if (first % 4 == 0) {
    rez += up / 2;
  }
  if (first % 4 == 1) {
    rez += up;
    rez += up / 2;
  }
  if (first % 4 == 2) {
    rez += (up + 1) / 2;
  }
  if (first % 4 == 3) {
    rez += up;
    rez += (up + 1) / 2;
  }
  return rez;
}
Ring<MOD> solveBigFastDef(long long n, long long m, long long first) {
  Ring<MOD> rez = 0;
  long long up = min(m, (first + 1) / 2);
  if (first % 4 == 0) {
    rez += up / 2;
  }
  if (first % 4 == 1) {
    rez += up;
    rez += up / 2;
  }
  if (first % 4 == 2) {
    rez += (up + 1) / 2;
  }
  if (first % 4 == 3) {
    rez += up;
    rez += (up + 1) / 2;
  }
  return rez;
}
Ring<MOD> quadSum(long long n) {
  n--;
  Ring<MOD> m = n;
  return m * (m + 1) * (2 * m + 1) / Ring<MOD>(6);
}
Ring<MOD> solveBigFast(long long n, long long m) {
  Ring<MOD> rez = 0;
  long long ton = 2 * m;
  long long ton2 = ton;
  while (ton2 % 4 != n % 4) {
    ton2++;
  }
  if (ton2 < n) {
    Ring<MOD> D = solveBigFastDef(n, m, n - 1) + solveBigFastDef(n, m, n - 2) +
                  solveBigFastDef(n, m, n - 3) + solveBigFastDef(n, m, n - 4);
    rez += Ring<MOD>(D) * Ring<MOD>((n - ton2)) / 4;
    rez += Ring<MOD>(solve(n, 0, 1, 2)) * Ring<MOD>(m);
    rez -= Ring<MOD>(solve(ton2, 0, 1, 2)) * Ring<MOD>(m);
    n = ton2;
  }
  while (n % 4 != 0 || n > ton) {
    rez += solveBigFast(n, m, n - 1);
    n--;
  }
  rez += solve(n / 4, 0, 1, 1);
  rez += quadSum(n / 4) * 4;
  rez += quadSum(n / 4) * 4;
  rez += solve(n / 4, 0, 2, 1);
  rez += solve(n / 4, 1, 2, 1);
  rez += solve(n / 4, 1, 2, 2);
  rez += solve(n / 4, 2, 2, 2);
  rez += quadSum(n / 4) * 4;
  rez += solve(n / 4, 1, 4, 1);
  rez += solve(n / 4, 2, 2, 2);
  rez += solve(n / 4, 2, 2, 1);
  rez += quadSum(n / 4) * 4;
  rez += solve(n / 4, 2, 6, 1);
  return rez;
}
Ring<MOD> _FinalCalcSum(long long n, long long m) {
  Ring<MOD> rez = solveBigFast(n, m);
  rez += solveBigFast(m, n);
  rez += calcSmallRect(n, m);
  for (pair<long long, long long> pp :
       {make_pair(0, 1), make_pair(1, 0), make_pair(1, 1), make_pair(2, 2)}) {
    if (pp.first < n && pp.second < m) {
      rez += 2;
    }
  }
  return rez;
}
void real() {
  long long tests;
  cin, tests;
  for (long long test = 0; test < tests; test++) {
    long long X, Y, N, M;
    cin, X, Y, N, M;
    smart_io::precall_print();
    cout, _FinalCalcSum(N, M) - _FinalCalcSum(N, Y - 1) -
              _FinalCalcSum(X - 1, M) + _FinalCalcSum(X - 1, Y - 1);
  }
}
signed main(signed argc, char *argv[]) {
  real();
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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>
template <class c>
int popc(c a) {
  if (sizeof(c) == 8)
    return __builtin_popcountll(a);
  else
    return __builtin_popcount(a);
}
template <class c>
int ctz(c a) {
  if (sizeof(c) == 8)
    return __builtin_ctzll(a);
  else
    return __builtin_ctz(a);
}
template <class c>
int clz(c a) {
  if (sizeof(c) == 8)
    return __builtin_clzll(a);
  else
    return __builtin_clz(a);
}
inline int min(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ first;
}
inline int max(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ second;
}
inline long long min(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ first;
}
inline long long max(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ second;
}
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace escape__from__random__aetuhoetnuhshe {
using namespace std::chrono;
mt19937 rng(duration_cast<milliseconds>(system_clock::now().time_since_epoch())
                .count());
uniform_real_distribution<> prob_dist(0.0, 1.0);
};  // namespace escape__from__random__aetuhoetnuhshe
namespace typedefs {}
namespace numbers_operation {
template <class T>
inline T floor_mod(T a, const T &b) {
  a %= b;
  if (a < 0) a += b;
  return a;
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
using namespace escape__from__random__aetuhoetnuhshe;
const long long MOD = 1e9 + 7;
long long mul(long long a, long long b) { return (1LL * a * b) % MOD; }
long long diff(long long a, long long b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
  return a;
}
void subt(long long &a, const long long &b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
}
long long sum(long long a, long long b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
  return a;
}
void add(long long &a, const long long &b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
}
long long power(long long a, long long deg) {
  long long res = 1;
  for (; deg; a = mul(a, a), deg >>= 1) {
    if (deg & 1) {
      res = mul(res, a);
    }
  }
  return res;
}
long long inverse(long long a) { return power(a, MOD - 2); }
long long _2 = inverse(2);
long long _6 = inverse(6);
long long divide(long long a, long long b) { return mul(a, inverse(b)); }
long long prog2(long long first) { return mul(mul(first, diff(first, 1)), _2); }
long long prog3(long long first) {
  return mul(mul(mul(first, diff(first, 1)), diff(mul(first, 2), 1)), _6);
}
long long magic_aux(long long sumL, long long sumR, long long sumStep,
                    long long cntL, long long cntStep) {
  if (sumR < sumL) {
    return 0;
  }
  long long stepCount = (sumR - sumL) / sumStep + 1;
  long long modSum = 0;
  add(modSum, mul(stepCount, cntL));
  add(modSum, mul(prog2(stepCount), cntStep));
  modSum = mul(modSum, sumL % 3);
  long long funcL = sumL / 3, funcStep = sumStep / 3;
  long long coeff0 = mul(cntL, funcL);
  long long coeff1 = sum(mul(cntL, funcStep), mul(funcL, cntStep));
  long long coeff2 = mul(cntStep, funcStep);
  long long divSum = 0;
  add(divSum, mul(coeff0, stepCount));
  add(divSum, mul(coeff1, prog2(stepCount)));
  add(divSum, mul(coeff2, prog3(stepCount)));
  long long res = sum(modSum, divSum);
  return res;
}
long long magic(long long sumL, long long sumR, long long sumStep,
                long long cntL, long long cntStep) {
  long long res = 0;
  for (long long it = 0; it < 3; ++it) {
    add(res, magic_aux(sumL + it * sumStep, sumR, 3 * sumStep,
                       cntL + cntStep * it, cntStep * 3));
  }
  return res;
}
long long seg2_aux(long long l, long long r) {
  if (l > r) {
    return 0;
  }
  long long r1 = l + 2 * (r - l) / 2;
  long long segCount = (r - l) / 2 + 1;
  long long res = magic(l, r1, 2, segCount, -1);
  return res;
}
long long seg2(long long l, long long r) {
  if (l > r) {
    return 0;
  }
  long long preRes = sum(seg2_aux(l, r), seg2_aux(l + 1, r));
  long long segLen = r - l + 1;
  long long segCount = (r - l) / 2 + 1;
  add(preRes, mul(segLen, prog2(segCount)));
  add(preRes, mul(MOD - 2, prog3(segCount)));
  return preRes;
}
long long calcSmallRect(long long first, long long second) {
  if (first < second) {
    swap(first, second);
  }
  long long rect1 = magic(0, second - 2, 1, 1, 1);
  long long rect2 = magic(second - 1, first - 1, 1, second, 0);
  long long rect3 = magic(first, first + second - 2, 1, second - 1, -1);
  long long right = seg2(1, second - 1);
  long long down = diff(seg2(1, first - 1),
                        seg2(2 * second + 1 + second, first - 1 + second));
  long long res = 0;
  add(res, rect1);
  add(res, rect2);
  add(res, rect3);
  subt(res, right);
  subt(res, down);
  return res;
}
long long f(long long first) { return first / 3 + first % 3; }
long long calcSmallRectStupid(long long first, long long second) {
  long long res = 0;
  for (long long i = 0; i < first; ++i) {
    for (long long j = 0; j < second; ++j) {
      if (2 * i >= j && 2 * j >= i) {
        res += f(i + j);
      }
    }
  }
  return res;
}
long long solveSmallSlow(long long n, long long m) {
  long long rez = 0;
  for (long long first = 0; first < n; first++) {
    for (long long second = 0; second < m; second++) {
      if (first <= 2 * second && second <= 2 * first) {
        if (first <= 2 * second && second <= 2 * first) {
          rez += (first + second) / 3;
          if ((first + second) % 3 == 1) {
            rez += 1;
          }
          if ((first + second) % 3 == 2) {
            rez += 2;
          }
        }
      }
    }
  }
  return rez;
}
template <long long MOD>
struct Ring {
  long long value = 0;
  Ring() {}
  Ring(long long _value) {
    value = _value;
    value = floor_mod(value, MOD);
  }
  Ring pow(long long p) const {
    Ring r = 1;
    Ring first;
    first.value = value;
    while (p) {
      if (p & 1) r *= first;
      first *= first;
      p /= 2;
    }
    return r;
  }
  Ring inv() const { return pow(MOD - 2); }
  void operator*=(const Ring<MOD> &b) {
    value *= b.value;
    value = floor_mod(value, MOD);
  }
  friend Ring operator*(Ring<MOD> a, const Ring<MOD> &b) {
    a *= b;
    return a;
  }
  void operator+=(const Ring<MOD> &b) {
    value += b.value;
    value -= (value >= MOD) * MOD;
  }
  friend Ring operator+(Ring a, const Ring &b) {
    a += b;
    return a;
  }
  void operator-=(const Ring<MOD> &b) {
    value -= b.value;
    value += (value < 0) ? MOD : 0;
  }
  friend Ring operator-(Ring a, const Ring &b) {
    a -= b;
    return a;
  }
  void operator/=(const Ring<MOD> &b) { (*this) *= b.inv(); }
  friend Ring operator/(Ring a, const Ring &b) {
    a /= b;
    return a;
  }
  bool operator==(const Ring<MOD> &b) { return value == b.value; }
  bool operator!=(const Ring<MOD> &b) { return value != b.value; }
  friend void fast_print(const Ring<MOD> &b) { fast_print(b.value); }
};
long long solve(long long n, long long a, long long b, long long m) {
  if (b == 0) return n * (a / m);
  if (a >= m) return n * (a / m) + solve(n, a % m, b, m);
  if (b >= m) return n * (n - 1) / 2 * (b / m) + solve(n, a, b % m, m);
  return solve((a + b * n) / m, (a + b * n) % m, m, b);
}
vector<pair<long long, long long>> shs;
Ring<MOD> solveBigFast(long long n, long long m, long long first) {
  Ring<MOD> rez = 0;
  long long up = min(m, (first + 1) / 2);
  rez += up * (first / 2);
  if (first % 4 == 0) {
    rez += up / 2;
  }
  if (first % 4 == 1) {
    rez += up;
    rez += up / 2;
  }
  if (first % 4 == 2) {
    rez += (up + 1) / 2;
  }
  if (first % 4 == 3) {
    rez += up;
    rez += (up + 1) / 2;
  }
  return rez;
}
Ring<MOD> solveBigFastDef(long long n, long long m, long long first) {
  Ring<MOD> rez = 0;
  long long up = min(m, (first + 1) / 2);
  if (first % 4 == 0) {
    rez += up / 2;
  }
  if (first % 4 == 1) {
    rez += up;
    rez += up / 2;
  }
  if (first % 4 == 2) {
    rez += (up + 1) / 2;
  }
  if (first % 4 == 3) {
    rez += up;
    rez += (up + 1) / 2;
  }
  return rez;
}
Ring<MOD> quadSum(long long n) {
  n--;
  Ring<MOD> m = n;
  return m * (m + 1) * (2 * m + 1) / Ring<MOD>(6);
}
Ring<MOD> solveBigFast(long long n, long long m) {
  Ring<MOD> rez = 0;
  long long ton = 2 * m;
  long long ton2 = ton;
  while (ton2 % 4 != n % 4) {
    ton2++;
  }
  if (ton2 < n) {
    Ring<MOD> D = solveBigFastDef(n, m, n - 1) + solveBigFastDef(n, m, n - 2) +
                  solveBigFastDef(n, m, n - 3) + solveBigFastDef(n, m, n - 4);
    rez += Ring<MOD>(D) * Ring<MOD>((n - ton2)) / 4;
    rez += Ring<MOD>(solve(n, 0, 1, 2)) * Ring<MOD>(m);
    rez -= Ring<MOD>(solve(ton2, 0, 1, 2)) * Ring<MOD>(m);
    n = ton2;
  }
  while (n % 4 != 0 || n > ton) {
    rez += solveBigFast(n, m, n - 1);
    n--;
  }
  rez += solve(n / 4, 0, 1, 1);
  rez += quadSum(n / 4) * 4;
  rez += quadSum(n / 4) * 4;
  rez += solve(n / 4, 0, 2, 1);
  rez += solve(n / 4, 1, 2, 1);
  rez += solve(n / 4, 1, 2, 2);
  rez += solve(n / 4, 2, 2, 2);
  rez += quadSum(n / 4) * 4;
  rez += solve(n / 4, 1, 4, 1);
  rez += solve(n / 4, 2, 2, 2);
  rez += solve(n / 4, 2, 2, 1);
  rez += quadSum(n / 4) * 4;
  rez += solve(n / 4, 2, 6, 1);
  return rez;
}
Ring<MOD> _FinalCalcSum(long long n, long long m) {
  Ring<MOD> rez = solveBigFast(n, m);
  rez += solveBigFast(m, n);
  rez += calcSmallRect(n, m);
  for (pair<long long, long long> pp :
       {make_pair(0, 1), make_pair(1, 0), make_pair(1, 1), make_pair(2, 2)}) {
    if (pp.first < n && pp.second < m) {
      rez += 2;
    }
  }
  return rez;
}
void real() {
  long long tests;
  cin, tests;
  for (long long test = 0; test < tests; test++) {
    long long X, Y, N, M;
    cin, X, Y, N, M;
    smart_io::precall_print();
    cout, _FinalCalcSum(N, M) - _FinalCalcSum(N, Y - 1) -
              _FinalCalcSum(X - 1, M) + _FinalCalcSum(X - 1, Y - 1);
  }
}
signed main(signed argc, char *argv[]) {
  real();
  return 0;
}

```