#include <bits/stdc++.h>
using namespace std;
const int mo = 1e9 + 7;
long long sum[100];
long long solve(int x, int y, int k, long long delta) {
  if (x <= 0 || y <= 0) return 0;
  if (x > y) swap(x, y);
  if (k < 0) return 0;
  int m = 0, len = 1;
  for (; len * 2 <= y; m++, len *= 2)
    ;
  if (len == y) {
    if (k >= len)
      return (1ll * (len + 1) * len / 2 % mo * x % mo +
              1ll * delta * len % mo * x % mo) %
             mo;
    else
      return (1ll * (k + 1) * k / 2 % mo * x % mo +
              1ll * delta * k % mo * x % mo) %
             mo;
  }
  long long ans = 0;
  if (x <= len) {
    ans = (ans + solve(x, len, k, delta)) % mo;
    ans = (ans + solve(x, y - len, k - len, delta + len)) % mo;
  } else {
    ans = (ans + solve(len, len, k, delta)) % mo;
    ans = (ans + solve(len, y - len, k - len, delta + len)) % mo;
    ans = (ans + solve(x - len, len, k - len, delta + len)) % mo;
    ans = (ans + solve(x - len, y - len, k, delta)) % mo;
  }
  return ans;
}
int main() {
  cin.sync_with_stdio(0);
  for (int i = 0; i < 30; ++i) {
    long long p = 1 << i;
    sum[i] = (p + 1) * p / 2 * p;
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    long long a1 = solve(x2, y2, k, 0);
    long long a2 = solve(x2, y1 - 1, k, 0);
    long long a3 = solve(x1 - 1, y2, k, 0);
    long long a4 = solve(x1 - 1, y1 - 1, k, 0);
    cout << ((a1 + a4 - a2 - a3) % mo + mo) % mo << endl;
  }
}
