func_code_string: #include <bits/stdc++.h>   using namespace std;   std::mt19937 rnd(       (int)std::chrono::steady_clock::now().time_since_epoch().count());   long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }   const int MOD = 1000000007;   void inc(int& a, int b) {     if ((a += b) >= MOD) a -= MOD;   }   void dec(int& a, int b) { inc(a, MOD - b); }   int qx, qy, xdim, ydim;   int inv[6 + 1];   int calcformula(int x, int y) {     int ret = max(max((x + 1) / 2, (y + 1) / 2), (x + y + 2) / 3);     if (ret % 2 != (x + y) % 2) ++ret;     return ret;   }   int calc(int x, int y) {     if (x == 1 && y == 0 || x == 0 && y == 1) return 3;     if (x == 1 && y == 1) return xdim > 3 || ydim > 3 ? 4 : 0;     if (x == 2 && y == 2) return 4;     if (x == 3 && y == 0 && xdim == 4 || x == 0 && y == 3 && ydim == 4) return 5;     return calcformula(x, y);   }   int divup(int num, int den) {     if (den < 0) num = -num, den = -den;     return num >= 0 ? (num + den - 1) / den : num / den;   }   int divdn(int num, int den) {     if (den < 0) num = -num, den = -den;     return num >= 0 ? num / den : (num - den + 1) / den;   }   int makesamepar(int a, int b) {     if ((a & 1) != (b & 1)) ++a;     return a;   }   int cnt(int lo, int hi) { return hi - lo + 1; }   int sum(int lo, int hi) {     return (long long)(lo + hi) * (hi - lo + 1) / 2 % MOD;   }   int sumsq(int n) {     return (long long)n * (n + 1) % MOD * (2 * n + 1) % MOD * inv[6] % MOD;   }   int sumsq(int lo, int hi) {     int ret = 0;     inc(ret, sumsq(hi));     if (lo != 0) dec(ret, sumsq(lo - 1));     return ret;   }   int calcsumstupid(int xlim, int ylim) {     int ret = 0;     for (int x = (0); x <= (xlim); ++x)       for (int y = (0); y <= (ylim); ++y) inc(ret, calc(x, y));     return ret;   }   int calcsum(int xlim, int ylim) {     int ret = 0;     for (int dx = (0); dx < (12); ++dx)       if (dx <= xlim)         for (int dy = (0); dy < (6); ++dy)           if (dy <= ylim) {             int A = (xlim - dx) / 12, B = (ylim - dy) / 6,                 D = divup(divup(dx, 2) - divup(dx + dy, 3), 2) - 1,                 E = makesamepar(divup(dx, 2), dx + dy);             int cur = 0;             {               int xlo = max(0, B - D), xhi = A, ylo = 0, yhi = B;               if (xlo <= xhi && ylo <= yhi) {                 cur = (cur + (long long)cnt(xlo, xhi) * cnt(ylo, yhi) % MOD * E) %                       MOD;                 cur = (cur + (long long)cnt(ylo, yhi) * sum(xlo, xhi) % MOD * 6) %                       MOD;               }             }             {               int xlo = max(0, -D), xhi = min(A, B - D - 1);               if (xlo <= xhi) {                 cur = (cur + (long long)cnt(xlo, xhi) * E % MOD * (D + 1)) % MOD;                 cur = (cur + (long long)sum(xlo, xhi) * E) % MOD;                 cur = (cur + (long long)sum(xlo, xhi) * 6 % MOD * (D + 1)) % MOD;                 cur = (cur + (long long)sumsq(xlo, xhi) * 6) % MOD;               }             }             inc(ret, cur);           }     for (int dx = (0); dx < (12); ++dx)       if (dx <= xlim)         for (int dy = (0); dy < (6); ++dy)           if (dy <= ylim) {             int A = (xlim - dx) / 12, B = (ylim - dy) / 6,                 C = divup(divup(dx, 2) - divup(dx + dy, 3), 2),                 D = divup(dx + dy, 3) - divup(dy, 2),                 E = makesamepar(divup(dx + dy, 3), dx + dy);             int cur = 0;             {               int xlo = max(0, divup(B - D, 4)), xhi = A, ylo = 0, yhi = B;               if (xlo <= xhi && ylo <= yhi) {                 cur = (cur + (long long)cnt(xlo, xhi) * cnt(ylo, yhi) % MOD * E) %                       MOD;                 cur = (cur + (long long)cnt(ylo, yhi) * sum(xlo, xhi) % MOD * 4) %                       MOD;                 cur = (cur + (long long)cnt(xlo, xhi) * sum(ylo, yhi) % MOD * 2) %                       MOD;               }             }             {               int xlo = max(0, divup(-D, 4)), xhi = min(A, divup(B - D, 4) - 1);               if (xlo <= xhi) {                 cur = (cur + (long long)cnt(xlo, xhi) * E % MOD * (D + 1)) % MOD;                 cur = (cur + (long long)sum(xlo, xhi) * E % MOD * 4) % MOD;                 cur = (cur + (long long)sumsq(xlo, xhi) * 16) % MOD;                 cur = (cur + (long long)sum(xlo, xhi) * (D + 1) % MOD * 4) % MOD;                 cur = (cur + (long long)sumsq(xlo, xhi) * 16) % MOD;                 cur = (cur + (long long)sum(xlo, xhi) * (2 * D + 1) % MOD * 4) %                       MOD;                 cur = (cur + (long long)cnt(xlo, xhi) * D % MOD * (D + 1)) % MOD;               }             }             {               int xlo = max(0, max(B - C + 1, divup(B - D, 4))), xhi = A, ylo = 0,                   yhi = B;               if (xlo <= xhi && ylo <= yhi) {                 cur = (cur -                        (long long)cnt(xlo, xhi) * cnt(ylo, yhi) % MOD * E % MOD +                        MOD) %                       MOD;                 cur = (cur -                        (long long)cnt(ylo, yhi) * sum(xlo, xhi) % MOD * 4 % MOD +                        MOD) %                       MOD;                 cur = (cur -                        (long long)cnt(xlo, xhi) * sum(ylo, yhi) % MOD * 2 % MOD +                        MOD) %                       MOD;               }             }             {               int xlo = max(0, max(1 - C, divup(C - D - 1, 3))),                   xhi = min(A, B - C);               if (xlo <= xhi) {                 cur = (cur - (long long)cnt(xlo, xhi) * E % MOD * C % MOD + MOD) %                       MOD;                 cur = (cur - (long long)sum(xlo, xhi) * E % MOD + MOD) % MOD;                 cur = (cur - (long long)sumsq(xlo, xhi) * 4 % MOD + MOD) % MOD;                 cur = (cur - (long long)sum(xlo, xhi) * C % MOD * 4 % MOD + MOD) %                       MOD;                 cur = (cur - (long long)sumsq(xlo, xhi) % MOD + MOD) % MOD;                 cur = (cur - (long long)sum(xlo, xhi) * (2 * C - 1) % MOD + MOD) %                       MOD;                 cur = (cur - (long long)cnt(xlo, xhi) * (C - 1) % MOD * C % MOD +                        MOD) %                       MOD;               }             }             {               int xlo = max(0, divup(-D, 4)),                   xhi = min(A, min(divup(B - D, 4) - 1, divup(C - D - 1, 3) - 1));               if (xlo <= xhi) {                 cur = (cur - (long long)cnt(xlo, xhi) * E % MOD * (D + 1) % MOD +                        MOD) %                       MOD;                 cur = (cur - (long long)sum(xlo, xhi) * E % MOD * 4 % MOD + MOD) %                       MOD;                 cur = (cur - (long long)sumsq(xlo, xhi) * 16 % MOD + MOD) % MOD;                 cur = (cur - (long long)sum(xlo, xhi) * (D + 1) % MOD * 4 % MOD +                        MOD) %                       MOD;                 cur = (cur - (long long)sumsq(xlo, xhi) * 16 % MOD + MOD) % MOD;                 cur = (cur -                        (long long)sum(xlo, xhi) * (2 * D + 1) % MOD * 4 % MOD +                        MOD) %                       MOD;                 cur = (cur - (long long)cnt(xlo, xhi) * D % MOD * (D + 1) % MOD +                        MOD) %                       MOD;               }             }             inc(ret, cur);           }     for (int dx = (0); dx < (6); ++dx)       if (dx <= xlim)         for (int dy = (0); dy < (12); ++dy)           if (dy <= ylim) {             int A = (xlim - dx) / 6, B = (ylim - dy) / 12,                 C = divdn(divup(dx + dy, 3) - divup(dy, 2), 2) + 1,                 E = makesamepar(divup(dy, 2), dx + dy);             int cur = 0;             {               int xlo = 0, xhi = min(A, -C), ylo = 0, yhi = B;               if (xlo <= xhi && ylo <= yhi) {                 cur = (cur + (long long)cnt(xlo, xhi) * cnt(ylo, yhi) % MOD * E) %                       MOD;                 cur = (cur + (long long)cnt(xlo, xhi) * sum(ylo, yhi) % MOD * 6) %                       MOD;               }             }             {               int xlo = max(0, -C + 1), xhi = min(A, B - C);               if (xlo <= xhi) {                 cur = (cur + (long long)cnt(xlo, xhi) * E % MOD * (B - C + 1)) %                       MOD;                 cur = (cur - (long long)sum(xlo, xhi) * E % MOD + MOD) % MOD;                 cur = (cur + (long long)cnt(xlo, xhi) * (C + B) % MOD *                                  (B - C + 1) % MOD * 3) %                       MOD;                 cur = (cur -                        (long long)sum(xlo, xhi) * (2 * C - 1) % MOD * 3 % MOD +                        MOD) %                       MOD;                 cur = (cur - (long long)sumsq(xlo, xhi) * 3 % MOD + MOD) % MOD;               }             }             inc(ret, cur);           }     vector<pair<int, int>> special;     special.push_back(make_pair(1, 0));     special.push_back(make_pair(0, 1));     special.push_back(make_pair(1, 1));     special.push_back(make_pair(3, 0));     special.push_back(make_pair(0, 3));     special.push_back(make_pair(2, 2));     for (int i = (0); i < (((int)(special).size())); ++i) {       int x, y;       tie(x, y) = special[i];       if (x <= xlim && y <= ylim) {         dec(ret, calcformula(x, y));         inc(ret, calc(x, y));       }     }     return ret;   }   void precalc() {     inv[1] = 1;     for (int i = (2); i <= (6); ++i)       inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;   }   int solve() {     int ret = 0;     inc(ret, calcsum(xdim - 1, ydim - 1));     dec(ret, calcsum(xdim - 1, qy - 1));     dec(ret, calcsum(qx - 1, ydim - 1));     inc(ret, calcsum(qx - 1, qy - 1));     return ret;   }   void run() {     scanf( %d%d%d%d , &qx, &qy, &xdim, &ydim);     --qx, --qy;     printf( %d n , solve());   }   void verifycalc() {     for (xdim = 3; xdim <= 20; ++xdim)       for (ydim = 3; ydim <= 20; ++ydim) {         vector<vector<int>> d(xdim, vector<int>(ydim, INT_MAX));         queue<pair<int, int>> q;         d[0][0] = 0, q.push(make_pair(0, 0));         while (!q.empty()) {           int x, y;           tie(x, y) = q.front();           q.pop();           for (int dx = (-2); dx <= (+2); ++dx)             for (int dy = (-2); dy <= (+2); ++dy)               if (dx * dx + dy * dy == 5) {                 int nx = x + dx, ny = y + dy;                 if (nx < 0 || nx >= xdim || ny < 0 || ny >= ydim) continue;                 if (d[nx][ny] == INT_MAX)                   d[nx][ny] = d[x][y] + 1, q.push(make_pair(nx, ny));               }         }         for (int x = (0); x < (xdim); ++x)           for (int y = (0); y < (ydim); ++y)             if (d[x][y] == INT_MAX) {               assert(xdim == 3 && ydim == 3 && x == 1 && y == 1);               d[x][y] = 0;             }         for (int x = (0); x < (xdim); ++x)           for (int y = (0); y < (ydim); ++y) assert(d[x][y] == calc(x, y));         printf( done (%d,%d) n , xdim, ydim);       }   }   void verifysum() {     for (xdim = 3; xdim <= 100; ++xdim) {       for (ydim = 3; ydim <= 100; ++ydim)         for (int dx = (1); dx <= (min(xdim, 3)); ++dx)           for (int dy = (1); dy <= (min(ydim, 3)); ++dy) {             int have = calcsum(xdim - dx, ydim - dy);             int want = calcsumstupid(xdim - dx, ydim - dy);             assert(have == want);           }       printf( done xdim=%d n , xdim);     }   }   int main() {     precalc();     int ncase;     scanf( %d , &ncase);     for (int i = (1); i <= (ncase); ++i) run();     return 0;   }   