#include <bits/stdc++.h>
using namespace std;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const int INF = 1 << 29;
const long long MOD = 1000000007;
int Q;
long long X1, Y1, X2, Y2, K;
long long aquery(long long times, long long pw, long long k, long long u) {
  if (times == 0 || pw == 0) {
    return 0;
  }
  if (u > k) {
    return 0;
  }
  long long lim = min(pw - 1, k - u);
  long long res = lim * (lim + 1) / 2 + (lim + 1) * u;
  res %= MOD;
  res *= times;
  res %= MOD;
  return res;
}
long long pquery(long long x, long long y, long long k, long long u) {
  if (x == 0 || y == 0) {
    return 0;
  }
  long long maxp = 1;
  while (maxp <= x || maxp <= y) maxp *= 2;
  maxp /= 2;
  if (x >= maxp && y >= maxp) {
    long long res = pquery(x - maxp, y - maxp, k, u);
    res += aquery(maxp, maxp, k, u);
    if (res >= MOD) res -= MOD;
    res += aquery(x - maxp, maxp, k, maxp + u);
    if (res >= MOD) res -= MOD;
    res += aquery(y - maxp, maxp, k, maxp + u);
    if (res >= MOD) res -= MOD;
    return res;
  } else if (x >= maxp) {
    long long res = pquery(x - maxp, y, k, maxp + u);
    res += aquery(y, maxp, k, u);
    if (res >= MOD) res -= MOD;
    return res;
  } else {
    long long res = pquery(x, y - maxp, k, maxp + u);
    res += aquery(x, maxp, k, u);
    if (res >= MOD) res -= MOD;
    return res;
  }
}
long long pquery(long long x, long long y, long long k) {
  return pquery(x, y, k, 1);
}
long long query(long long x1, long long y1, long long x2, long long y2,
                long long k) {
  long long res = pquery(x2, y2, k) - pquery(x1, y2, k) - pquery(x2, y1, k) +
                  pquery(x1, y1, k);
  res %= MOD;
  if (res < 0) res += MOD;
  return res;
}
int main() {
  cin >> Q;
  for (int q = 0; q < (Q); ++q) {
    cin >> X1 >> Y1 >> X2 >> Y2 >> K;
    cout << query(X1 - 1, Y1 - 1, X2, Y2, K) << '\n';
  }
  return 0;
}
