#include <bits/stdc++.h>
using namespace std;
const int maxs = 40;
const int N = 30;
const int Mo = 1000000007;
int f[maxs][2][2][2], g[maxs][2][2][2];
int DP(int n, int m, int K) {
  K--, n--, m--;
  if (K < 0 || n < 0 || m < 0) return 0;
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  g[N + 1][1][1][1] = 1;
  int s, sn, sm, sk, i, j, k, x, y, z, ii, jj, kk, gg, ff;
  for (s = N; s >= 0; --s) {
    sn = ((n >> s) & 1), sm = ((m >> s) & 1), sk = ((K >> s) & 1);
    for (i = 0; i < 2; ++i) {
      for (j = 0; j < 2; ++j) {
        for (k = 0; k < 2; ++k) {
          gg = g[s + 1][i][j][k], ff = f[s + 1][i][j][k];
          if (gg + ff == 0) continue;
          for (x = 0; x < 2; ++x) {
            for (y = 0; y < 2; ++y) {
              z = (x ^ y), ii = i, jj = j, kk = k;
              if (i && x < sn) ii = 0;
              if (i && x > sn) continue;
              if (j && y < sm) jj = 0;
              if (j && y > sm) continue;
              if (k && z < sk) kk = 0;
              if (k && z > sk) continue;
              g[s][ii][jj][kk] = (g[s][ii][jj][kk] + gg) % Mo;
              f[s][ii][jj][kk] =
                  (1LL * z * (1 << s) * gg + ff + f[s][ii][jj][kk]) % Mo;
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 2; ++k) {
        ans = ((long long)ans + f[0][i][j][k] + g[0][i][j][k]) % Mo;
      }
    }
  }
  return ans;
}
int main() {
  int sumt, x1, y1, x2, y2, k;
  scanf("%d", &sumt);
  while (sumt--) {
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    int ans = (DP(x2, y2, k) + DP(x1 - 1, y1 - 1, k)) % Mo;
    ans = (ans - DP(x1 - 1, y2, k)) % Mo;
    ans = (ans - DP(x2, y1 - 1, k)) % Mo;
    ans = (ans % Mo + Mo) % Mo;
    printf("%d\n", ans);
  }
  return 0;
}
