#include <bits/stdc++.h>
using namespace std;
long long calc1(long long x, long long y, long long k) {
  if (k < 1 || y == 0 || x == 0) return 0;
  if (x > y) swap(x, y);
  int u = 63 - __builtin_clzll(y), v = 63 - __builtin_clzll(x);
  long long c = (1LL << u), d = (1LL << v);
  if (c > d) {
    if (k <= c) return k * x % 1000000007;
    return c * x % 1000000007 + calc1(x, y - c, k - c);
  } else {
    long long kk = min(k, c), ans = kk * c % 1000000007;
    ans += calc1(x - c, c, k - c);
    ans += calc1(y - c, c, k - c);
    ans += calc1(x - c, y - c, k);
    return ans %= 1000000007;
  }
}
long long inv2 = 500000004LL;
long long calc(long long x, long long y, long long k) {
  if (k < 1 || y == 0 || x == 0) return 0;
  if (x > y) swap(x, y);
  int u = 63 - __builtin_clzll(y), v = 63 - __builtin_clzll(x);
  long long c = (1LL << u), d = (1LL << v);
  if (c > d) {
    long long f = min(c, k);
    return ((f + 1) * f / 2 % 1000000007 * x % 1000000007 +
            calc(x, y - c, k - c) + c * calc1(x, y - c, k - c)) %
           1000000007;
  } else {
    long long f = min(k, c),
              ans = (f + 1LL) * f / 2 % 1000000007 * c % 1000000007;
    ans += calc(d, y - c, k - c) + c * calc1(d, y - c, k - c) % 1000000007;
    ans += calc(c, x - d, k - d) + c * calc1(c, x - d, k - d) % 1000000007;
    ans += calc(x - c, y - c, k);
    return ans % 1000000007;
  }
}
int main() {
  int Q;
  long long x1, y1, x2, y2, k;
  for (scanf("%d", &Q); Q--;) {
    scanf("%I64d %I64d %I64d %I64d %I64d", &x1, &y1, &x2, &y2, &k);
    long long ans = calc(x2, y2, k);
    ans -= calc(x1 - 1, y2, k);
    ans -= calc(x2, y1 - 1, k);
    ans += calc(x1 - 1, y1 - 1, k);
    ans %= 1000000007;
    if (ans < 0) ans += 1000000007;
    printf("%I64d\n", ans);
  }
  return 0;
}
