#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)(1e9 + 7);
long long INV2;
long long mul(long long a, long long b) { return (a * b) % MOD; }
long long pw(long long a, long long b) {
  long long ans = 1;
  for (; b; b >>= 1, a = mul(a, a)) {
    if (b & 1) {
      ans = mul(ans, a);
    }
  }
  return ans;
}
struct Node {
  int x, y, k;
  long long v;
  Node() {}
  Node(int _x, int _y, int _k, int _v) : x(_x), y(_y), k(_k), v(_v) {}
  bool operator<(const Node& rhs) const {
    if (x != rhs.x) return x < rhs.x;
    if (y != rhs.y) return y < rhs.y;
    if (k != rhs.k) return k < rhs.k;
    return v < rhs.v;
  }
};
map<Node, long long> Cache;
long long calc(int x, int y, long long k, long long v) {
  if (x <= 0 || y <= 0 || k <= 0) {
    return 0;
  }
  Node hash_val(x, y, k, v);
  if (Cache.count(hash_val)) return Cache[hash_val];
  int d = 0;
  for (; (1LL << d) < max(x, y); ++d) {
  }
  long long f = (1LL << d);
  if ((x == f || y == f) && f <= k) {
    if (y == f) swap(x, y);
    long long a = mul(y, mul(f, mul(f + 1, INV2)));
    long long b = mul(y, mul(f, v));
    return Cache[hash_val] = (a + b) % MOD;
  }
  long long ans = 0;
  long long m = (1LL << (d - 1));
  ans = (ans + calc(min(m, 1LL * x), min(m, 1LL * y), k, v)) % MOD;
  ans = (ans + calc(x - m, min(m, 1LL * y), k - m, (v + m) % MOD)) % MOD;
  ans = (ans + calc(min(m, 1LL * x), y - m, k - m, (v + m) % MOD)) % MOD;
  ans = (ans + calc(x - m, y - m, k, v)) % MOD;
  return Cache[hash_val] = ans;
}
int main() {
  INV2 = pw(2, MOD - 2);
  int q, x1, y1, x2, y2;
  long long k;
  cin >> q;
  while (q--) {
    scanf("%d%d%d%d%lld", &x1, &y1, &x2, &y2, &k);
    long long ans = calc(x2, y2, k, 0);
    ans = (ans + MOD - calc(x2, y1 - 1, k, 0)) % MOD;
    ans = (ans + MOD - calc(x1 - 1, y2, k, 0)) % MOD;
    ans = (ans + calc(x1 - 1, y1 - 1, k, 0)) % MOD;
    printf("%lld\n", ans);
  }
  return 0;
}
