#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;
const long long INFL = 1001001001001001001LL;
template <typename T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
int in() {
  int x;
  cin >> x;
  return x;
}
double fin() {
  double x;
  cin >> x;
  return x;
}
string sin() {
  string x;
  cin >> x;
  return x;
}
long long lin() {
  long long x;
  cin >> x;
  return x;
}
long long mod = 1000000007;
long long solve(long long n, long long x1, long long y1, long long x2,
                long long y2, long long k, long long plus) {
  if (0 > x2 || 0 > y2 || n - 1 < x1 || n - 1 < y1 || plus >= k) return 0;
  if (x1 <= 0 && n - 1 <= x2 && y1 <= 0 && n - 1 <= y2) {
    long long a = min(plus + n, k);
    long long b = plus + 1;
    long long sol = (a + b) * (a - b + 1) / 2 % mod * n % mod;
    return sol;
  } else if (x1 <= 0 && n - 1 <= x2) {
    long long a = min(plus + n, k);
    long long b = plus + 1;
    long long my1 = max(0LL, y1);
    long long my2 = min(n - 1, y2);
    long long sol = (a + b) * (a - b + 1) / 2 % mod * (my2 - my1 + 1) % mod;
    return sol;
  } else if (y1 <= 0 && n - 1 <= y2) {
    long long a = min(plus + n, k);
    long long b = plus + 1;
    long long mx1 = max(0LL, x1);
    long long mx2 = min(n - 1, x2);
    long long sol = (a + b) * (a - b + 1) / 2 % mod * (mx2 - mx1 + 1) % mod;
    return sol;
  } else {
    long long m = n / 2;
    long long sol1 = solve(m, x1, y1, x2, y2, k, plus);
    long long sol2 = solve(m, x1 - m, y1, x2 - m, y2, k, plus + m);
    long long sol3 = solve(m, x1, y1 - m, x2, y2 - m, k, plus + m);
    long long sol4 = solve(m, x1 - m, y1 - m, x2 - m, y2 - m, k, plus);
    return (sol1 + sol2 + sol3 + sol4) % mod;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int q = in();
  for (int cs = 0; cs < (int)(q); ++cs) {
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    x1--;
    y1--;
    x2--;
    y2--;
    long long cur = 1;
    while (cur <= x2 || cur <= y2) cur <<= 1;
    cout << solve(cur, x1, y1, x2, y2, k, 0) << '\n';
  }
  return 0;
}
