#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int mxn = 10005;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int x[35], y[35], k[35], len;
long long cnt[33][2][2][2];
long long f[33][2][2][2];
long long calc(int X, int Y, int K) {
  if (X < Y) swap(X, Y);
  if (!X || !Y) return 0;
  K--;
  X--;
  Y--;
  len = 31;
  int i, j;
  for (i = 1; i <= len; i++) {
    k[i] = K & 1;
    K >>= 1;
  }
  for (i = 1; i <= len; i++) {
    y[i] = Y & 1;
    Y >>= 1;
  }
  for (i = 1; i <= len; i++) {
    x[i] = X & 1;
    X >>= 1;
  }
  memset(cnt, 0, sizeof cnt);
  memset(f, 0, sizeof f);
  cnt[32][0][0][0] = 1;
  for (i = 31; i; i--) {
    for (int c1 = 0; c1 < 2; c1++)
      for (int c2 = 0; c2 < 2; c2++)
        for (int nk = 0; nk < 2; nk++)
          for (int a = 0; a <= (c1 ? 1 : x[i]); a++) {
            for (int b = 0; b <= (c2 ? 1 : y[i]); b++) {
              if ((a ^ b) > (nk ? 1 : k[i])) continue;
              int t1 = c1 | (a < x[i]), t2 = c2 | (b < y[i]),
                  t3 = nk | ((a ^ b) < k[i]);
              (cnt[i][t1][t2][t3] += cnt[i + 1][c1][c2][nk]) %= mod;
              (f[i][t1][t2][t3] +=
               f[i + 1][c1][c2][nk] +
               (((a ^ b) << (i - 1)) % mod * cnt[i + 1][c1][c2][nk]) % mod) %=
                  mod;
            }
          }
  }
  long long smm = 0, g = 0;
  for (int c1 = 0; c1 < 2; c1++)
    for (int c2 = 0; c2 < 2; c2++)
      for (int nk = 0; nk < 2; nk++) {
        smm += f[1][c1][c2][nk];
        if (smm >= mod) smm -= mod;
        g += cnt[1][c1][c2][nk];
        if (g >= mod) g -= mod;
      }
  return (smm + g) % mod;
}
int main() {
  int i, j, x1, x2, y1, y2, k;
  int Q = read();
  while (Q--) {
    x1 = read();
    y1 = read();
    x2 = read();
    y2 = read();
    k = read();
    long long ans = ((long long)calc(x2, y2, k) - calc(x1 - 1, y2, k) -
                     calc(x2, y1 - 1, k) + calc(x1 - 1, y1 - 1, k)) %
                    mod;
    ans = (ans + mod) % mod;
    printf("%I64d\n", ans);
  }
  return 0;
}
