#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
inline long long sum(long long x, long long y, long long off, long long k) {
  long long lo = off + 1;
  long long hi = min(k, off + x);
  if (hi < lo) return 0;
  long long ret = (lo * (hi - lo + 1) + (hi - lo) * (hi - lo + 1) / 2) % mod;
  (ret *= y) %= mod;
  return ret % mod;
}
inline long long getSum(long long x, long long y, long long off, long long k) {
  if (y > x) {
    long long ret = sum(x, x, off, k);
    ret += sum(x, y - x, off ^ x, k);
    if (ret >= mod) ret -= mod;
    return ret;
  }
  return sum(x, y, off, k);
}
long long compute(long long x, long long y, long long off, long long k) {
  if (x < y) swap(x, y);
  long long p = 1;
  while (p * 2 <= x) p *= 2;
  if (x == p) {
    return getSum(p, y, off, k);
  } else {
    long long ret = getSum(p, y, off, k);
    ret += compute(x - p, y, off ^ p, k);
    if (ret >= mod) ret -= mod;
    return ret;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << setprecision(32);
  int q;
  cin >> q;
  while (q--) {
    long long x1, x2, y1, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    long long ans = compute(x2, y2, 0, k);
    if (x1 > 1) ans += mod - compute(x1 - 1, y2, 0, k);
    if (y1 > 1) ans += mod - compute(x2, y1 - 1, 0, k);
    if (x1 > 1 && y1 > 1) ans += compute(x1 - 1, y1 - 1, 0, k);
    ans %= mod;
    cout << ans << '\n';
  }
  return 0;
}
