#include <bits/stdc++.h>
using namespace std;
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int xbits[32], ybits[32], kbits[32];
long long DP_sum[32][2][2][2], DP_cnt[32][2][2][2];
long long dp_cnt(int i, int xless, int yless, int kless) {
  if (i == -1) return 1;
  long long &ans = DP_cnt[i][xless][yless][kless];
  if (ans != -1) return ans;
  ans = 0;
  for (int next_x = 0; next_x < 2; next_x++) {
    if (xless == 0 && next_x > xbits[i]) continue;
    int new_xless = xless | (next_x < xbits[i]);
    for (int next_y = 0; next_y < 2; next_y++) {
      if (yless == 0 && next_y > ybits[i]) continue;
      int new_yless = yless | (next_y < ybits[i]);
      int next_k = next_x ^ next_y;
      if (kless == 0 && next_k > kbits[i]) continue;
      int new_kless = kless | (next_k < kbits[i]);
      ans += dp_cnt(i - 1, new_xless, new_yless, new_kless);
      ans %= (1000000007LL);
    }
  }
  return ans;
}
long long dp_sum(int i, int xless, int yless, int kless) {
  if (i == -1) return 0;
  long long &ans = DP_sum[i][xless][yless][kless];
  if (ans != -1) return ans;
  ans = 0;
  for (int next_x = 0; next_x < 2; next_x++) {
    if (xless == 0 && next_x > xbits[i]) continue;
    int new_xless = xless | (next_x < xbits[i]);
    for (int next_y = 0; next_y < 2; next_y++) {
      if (yless == 0 && next_y > ybits[i]) continue;
      int new_yless = yless | (next_y < ybits[i]);
      int next_k = next_x ^ next_y;
      if (kless == 0 && next_k > kbits[i]) continue;
      int new_kless = kless | (next_k < kbits[i]);
      ans += dp_sum(i - 1, new_xless, new_yless, new_kless) +
             (next_k) * (1LL << i) *
                 dp_cnt(i - 1, new_xless, new_yless, new_kless);
      ans %= (1000000007LL);
    }
  }
  return ans;
}
long long solve(int x, int y, int k) {
  if (x < 0 || y < 0) return 0;
  int logn = 31;
  for (int i = 0; i < logn; i++) {
    xbits[i] = x % 2;
    x /= 2;
    ybits[i] = y % 2;
    y /= 2;
    kbits[i] = k % 2;
    k /= 2;
  }
  memset(DP_sum, -1, sizeof(DP_sum));
  memset(DP_cnt, -1, sizeof(DP_cnt));
  long long ans = dp_sum(logn - 1, 0, 0, 0) + dp_cnt(logn - 1, 0, 0, 0);
  return ans % (1000000007LL);
}
int main() {
  int q;
  scanf("%d", &q);
  while (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 = solve(x2, y2, k) - solve(x1 - 1, y2, k) -
                    solve(x2, y1 - 1, k) + solve(x1 - 1, y1 - 1, k);
    ans %= (1000000007LL);
    ans += (1000000007LL);
    ans %= (1000000007LL);
    printf("%lld\n", ans);
  }
  return 0;
}
