#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int bitx[32], bity[32], bitk[32];
long long dp[32][2][2][2], dp1[32][2][2][2], f[32];
pair<long long, long long> dfs(int pos, int limit1, int limit2, int limit3) {
  if (pos == 0) return make_pair(1, 0);
  if (dp[pos][limit1][limit2][limit3] != -1)
    return make_pair(dp[pos][limit1][limit2][limit3],
                     dp1[pos][limit1][limit2][limit3]);
  int x = limit1 ? bitx[pos] : 1;
  int y = limit2 ? bity[pos] : 1;
  long long ret = 0;
  long long ret1 = 0;
  for (int i = 0; i <= x; ++i) {
    for (int j = 0; j <= y; ++j) {
      if (limit3 && (i ^ j) > bitk[pos]) continue;
      pair<long long, long long> t =
          dfs(pos - 1, limit1 && (i == x), limit2 && (j == y),
              limit3 && ((i ^ j) == bitk[pos]));
      (ret += t.first) %= mod;
      (ret1 += t.second + ((i ^ j) ? f[pos - 1] : 0) * t.first % mod) %= mod;
    }
  }
  dp[pos][limit1][limit2][limit3] = ret,
  dp1[pos][limit1][limit2][limit3] = ret1;
  return make_pair(ret, ret1);
}
long long solve(long long x, long long y, long long k) {
  memset(dp, -1, sizeof(dp));
  if (x < 0 || y < 0) return 0;
  memset(bitx, 0, sizeof(bitx));
  memset(bity, 0, sizeof(bity));
  memset(bitk, 0, sizeof(bitk));
  int lenx = 0;
  while (x) {
    bitx[++lenx] = x & 1;
    x >>= 1;
  }
  int leny = 0;
  while (y) {
    bity[++leny] = y & 1;
    y >>= 1;
  }
  int lenk = 0;
  while (k) {
    bitk[++lenk] = k & 1;
    k >>= 1;
  }
  pair<long long, long long> t = dfs(31, 1, 1, 1);
  return (t.first + t.second) % mod;
}
int main() {
  f[0] = 1;
  for (int i = 1; i < 31; ++i) f[i] = f[i - 1] * 2 % mod;
  int T, x1, y1, x2, y2, k;
  scanf("%d", &T);
  memset(dp, -1, sizeof(dp));
  while (T--) {
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    x1--;
    y1--;
    x2--;
    y2--;
    k--;
    printf("%I64d\n", ((solve(x2, y2, k) - solve(x1 - 1, y2, k) -
                        solve(x2, y1 - 1, k) + solve(x1 - 1, y1 - 1, k)) %
                           mod +
                       mod) %
                          mod);
  }
  return 0;
}
