#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
long long f[33][2][2][2], g[33][2][2][2];
int dig1[33], dig2[33], dig3[33], k;
pair<long long, long long> dfs(int pos, int st1, int st2, int st3) {
  if (pos == -1) return make_pair(1, 0);
  if (f[pos][st1][st2][st3] != -1)
    return make_pair(f[pos][st1][st2][st3], g[pos][st1][st2][st3]);
  long long ans = 0;
  long long sum = 0;
  int n1 = st1 ? 1 : dig1[pos];
  int n2 = st2 ? 1 : dig2[pos];
  for (int i = 0; i <= n1; i++) {
    for (int j = 0; j <= n2; j++) {
      int now_st1 = st1 || i < n1;
      int now_st2 = st2 || j < n2;
      int now_st3 = st3 || (i ^ j) < dig3[pos];
      if (st3 == 0 && (i ^ j) > dig3[pos]) continue;
      pair<long long, long long> res = dfs(pos - 1, now_st1, now_st2, now_st3);
      sum += (i ^ j) * res.first * 1ll * (1 << pos) % mod + res.second % mod;
      ans += res.first;
    }
  }
  ans %= mod;
  sum %= mod;
  return make_pair(f[pos][st1][st2][st3] = ans, g[pos][st1][st2][st3] = sum);
}
long long cal(int x, int y) {
  memset(f, -1, sizeof f);
  memset(g, -1, sizeof g);
  memset(dig1, 0, sizeof dig1);
  memset(dig2, 0, sizeof dig2);
  int pos = 0;
  while (x) dig1[pos++] = x & 1, x >>= 1;
  pos = 0;
  while (y) dig2[pos++] = y & 1, y >>= 1;
  pair<long long, long long> ans = dfs(30, 0, 0, 0);
  return ans.first + ans.second;
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int x1, y1, x2, y2;
    scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &k);
    memset(dig3, 0, sizeof dig3);
    x1--, x2--, y1--, y2--;
    int pos = 0, p = k - 1;
    while (p) dig3[pos++] = p & 1, p >>= 1;
    long long ans = 0;
    ans += cal(x2, y2);
    if (x1) ans -= cal(x1 - 1, y2);
    if (y1) ans -= cal(x2, y1 - 1);
    if (x1 && y1) ans += cal(x1 - 1, y1 - 1);
    ans %= mod;
    if (ans < 0) ans += mod;
    printf("%lld\n", ans);
  }
  return 0;
}
