#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long)1e+9 + 7ll;
const long long linf = (long long)1e+18 + 7ll;
const long double eps = (long double)1e-9;
const long double pi = acosl((long double)-1.0);
const int alph = 26;
static char buff[(int)2e6 + 17];
const int maxn = (int)3e5 + 17;
int q;
long long dp[35][2][2][2], sm[35][2][2][2];
void add(long long& x, long long y) { x += y, x %= inf; }
void sub(long long& x, long long y) {
  x %= inf, y %= inf, x -= y, x += inf, x %= inf;
}
long long mul(long long x, long long y) {
  return x %= inf, y %= inf, x *= y, x %= inf, x;
}
bool read() {
  if (scanf("%d", &q) != 1) return false;
  return true;
}
vector<int> calc(int x) {
  vector<int> res;
  for (int i = 0; i < 34; ++i, x /= 2) res.push_back(x % 2);
  reverse(res.begin(), res.end());
  return res;
}
long long get(int x, int y, int k) {
  if (x < 0 || y < 0 || k < 0) return 0;
  memset(dp, 0, sizeof(dp));
  memset(sm, 0, sizeof(sm));
  vector<int> X = calc(x), Y = calc(y), K = calc(k);
  dp[0][1][1][1] = 1;
  for (int i = 0; i < 34; ++i)
    for (int a = 0; a <= 1; ++a)
      for (int b = 0; b <= 1; ++b)
        for (int c = 0; c <= 1; ++c)
          for (int x = 0; x <= 1; ++x)
            for (int y = 0; y <= 1; ++y) {
              long long z = x ^ y;
              if (a && x > X[i]) continue;
              if (b && y > Y[i]) continue;
              if (c && z > K[i]) continue;
              add(dp[i + 1][a & (x == X[i])][b & (y == Y[i])][c & (z == K[i])],
                  dp[i][a][b][c]);
              add(sm[i + 1][a & (x == X[i])][b & (y == Y[i])][c & (z == K[i])],
                  sm[i][a][b][c]);
              add(sm[i + 1][a & (x == X[i])][b & (y == Y[i])][c & (z == K[i])],
                  mul((z << (33 - i)), dp[i][a][b][c]));
            }
  long long res = 0;
  for (int a = 0; a <= 1; ++a)
    for (int b = 0; b <= 1; ++b)
      for (int c = 0; c <= 1; ++c) {
        add(res, dp[34][a][b][c]);
        add(res, sm[34][a][b][c]);
      }
  return res;
}
void solve() {
  for (; q > 0; --q) {
    int x1, y1, x2, y2, k;
    scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &k);
    --x1, --y1, --x2, --y2, --k;
    long long ans = 0;
    add(ans, get(x2, y2, k));
    add(ans, get(x1 - 1, y1 - 1, k));
    sub(ans, get(x2, y1 - 1, k));
    sub(ans, get(x1 - 1, y2, k));
    printf("%lld\n", ans);
  }
}
int main() {
  while (read()) solve();
  return 0;
}
