#include <bits/stdc++.h>
using namespace std;
set<long long> p2;
bool isP2(long long c) {
  if (p2.find(c) != p2.end()) return true;
  return false;
}
long long getSum(long long x) { return ((x + 1) * x / 2) % 1000000007; }
long long getAm(long long x, long long y, long long k) {
  if (k <= 0) return 0;
  if (x <= 0 || y <= 0) return 0;
  if (x < y) swap(x, y);
  if (isP2(x)) {
    long long minAm = min(k, x);
    return (minAm * y) % 1000000007;
  }
  long long cP2 = 1;
  while (cP2 < x || cP2 < y) cP2 *= 2;
  cP2 /= 2;
  return (getAm(min(x, cP2), min(y, cP2), k) + getAm(x - cP2, y - cP2, k) +
          getAm(x - cP2, min(y, cP2), k - cP2) +
          getAm(min(x, cP2), y - cP2, k - cP2)) %
         1000000007;
}
long long getSum(long long x, long long y, long long k) {
  if (k <= 0) return 0;
  if (x <= 0 || y <= 0) return 0;
  if (x < y) swap(x, y);
  if (isP2(x)) {
    long long minAm = min(k, x);
    return (getSum(minAm) * y) % 1000000007;
  }
  long long cP2 = 1;
  while (cP2 < x || cP2 < y) cP2 *= 2;
  cP2 /= 2;
  long long ans = getSum(min(x, cP2), min(y, cP2), k);
  ans += getSum(x - cP2, y - cP2, k);
  ans += getSum(x - cP2, min(y, cP2), k - cP2) +
         (cP2 * getAm(x - cP2, min(y, cP2), k - cP2)) % 1000000007;
  ans += getSum(min(x, cP2), y - cP2, k - cP2) +
         (cP2 * getAm(min(x, cP2), y - cP2, k - cP2)) % 1000000007;
  ans %= 1000000007;
  return ans % 1000000007;
}
int Q;
int main() {
  scanf("%d", &Q);
  long long cP2 = 1;
  for (int(i) = (0); (i) < (40); ++(i)) {
    p2.insert(cP2);
    cP2 *= 2;
  }
  for (int(i) = (0); (i) < (Q); ++(i)) {
    long long x1, x2, y1, y2, k;
    scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &k);
    long long ans = getSum(x2, y2, k) - getSum(x1 - 1, y2, k) -
                    getSum(x2, y1 - 1, k) + getSum(x1 - 1, y1 - 1, k);
    ans %= 1000000007;
    while (ans < 0) ans += 1000000007;
    printf("%lld\n", ans);
  }
  return 0;
}
