#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char a = getchar();
  while (a < '0' || a > '9') {
    if (a == '-') f = -1;
    a = getchar();
  }
  while (a >= '0' && a <= '9') x = x * 10 + a - '0', a = getchar();
  return x * f;
}
int solve(int x, int y, int k, int add) {
  if (x > y) swap(x, y);
  if (!x) return 0;
  if (k <= 0) return 0;
  int z = 1 << (31 - __builtin_clz(y)), kk = min(k, z), ret = 0;
  if (x < z) {
    ret += (((1LL * (kk + 1) * kk / 2 % 1000000007) * x) % 1000000007 +
            ((1LL * kk * add) % 1000000007 * x) % 1000000007) %
           1000000007;
    (ret += solve(x, y - z, k - z, add + z)) %= 1000000007;
  } else {
    ret += (((1LL * (kk + 1) * kk / 2 % 1000000007) * z) % 1000000007 +
            ((1LL * kk * add) % 1000000007 * z) % 1000000007) %
           1000000007;
    (ret += solve(z, y - z, k - z, add + z)) %= 1000000007;
    (ret += solve(x - z, z, k - z, add + z)) %= 1000000007;
    (ret += solve(x - z, y - z, k, add)) %= 1000000007;
  }
  return ret;
}
int main() {
  int q, x1, x2, y1, y2, k, ans;
  q = read();
  while (q--) {
    x1 = read() - 1;
    y1 = read() - 1;
    x2 = read();
    y2 = read();
    k = read();
    ans = 0;
    (ans += (solve(x1, y1, k, 0) + solve(x2, y2, k, 0)) % 1000000007) %=
        1000000007;
    (ans -= (solve(x1, y2, k, 0) + solve(x2, y1, k, 0)) % 1000000007) %=
        1000000007;
    printf("%d\n", (ans + 1000000007) % 1000000007);
  }
  return 0;
}
