#include <bits/stdc++.h>
using namespace std;
const long long mo = 1e9 + 7;
long long _;
long long x1, kjhjk, x2, dfdfd, k;
long long a[40], b[40], c[40];
long long dp1[40][2][2][2], dp2[40][2][2][2];
long long solve(long long x, long long y) {
  if (x < 0 || y < 0 || k < 0) return 0;
  long long i;
  memset(dp1, 0, sizeof(dp1));
  memset(dp2, 0, sizeof(dp2));
  long long xx = x, yy = y, kk = k;
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  memset(c, 0, sizeof(c));
  for (i = 0; i < 31; i++) {
    a[i] = xx % 2;
    xx /= 2;
    b[i] = yy % 2;
    yy /= 2;
    c[i] = kk % 2;
    kk /= 2;
  }
  reverse(a, a + 31);
  reverse(b, b + 31);
  reverse(c, c + 31);
  long long A, B, C, X, Y, Z;
  dp1[0][1][1][1] = 1;
  for (i = 0; i < 31; i++)
    for (A = 0; A < 2; A++)
      for (B = 0; B < 2; B++)
        for (C = 0; C < 2; C++)
          for (X = 0; X < 2; X++)
            for (Y = 0; Y < 2; Y++) {
              Z = X ^ Y;
              if (A == 1 && X == 1 && a[i] == 0) continue;
              if (B == 1 && Y == 1 && b[i] == 0) continue;
              if (C == 1 && Z == 1 && c[i] == 0) continue;
              (dp1[i + 1][A & (a[i] == X)][B & (b[i] == Y)][C & (c[i] == Z)] +=
               dp1[i][A][B][C]) %= mo;
              (dp2[i + 1][A & (a[i] == X)][B & (b[i] == Y)][C & (c[i] == Z)] +=
               dp2[i][A][B][C]) %= mo;
              (dp2[i + 1][A & (a[i] == X)][B & (b[i] == Y)][C & (c[i] == Z)] +=
               dp1[i][A][B][C] % mo * ((Z << (30 - i)) % mo) % mo) %= mo;
            }
  long long sum = 0;
  for (A = 0; A < 2; A++)
    for (B = 0; B < 2; B++)
      for (C = 0; C < 2; C++) {
        (sum += dp1[31][A][B][C]) %= mo;
        (sum += dp2[31][A][B][C]) %= mo;
      }
  return sum;
}
int main() {
  scanf("%lld", &_);
  while (_--) {
    scanf("%lld%lld%lld%lld%lld", &x1, &kjhjk, &x2, &dfdfd, &k);
    x1--;
    kjhjk--;
    x2--;
    dfdfd--;
    k--;
    printf("%lld\n",
           (solve(x2, dfdfd) - solve(x1 - 1, dfdfd) - solve(x2, kjhjk - 1) +
            solve(x1 - 1, kjhjk - 1) + mo * 10) %
               mo);
  }
  return 0;
}
