#include <bits/stdc++.h>
using namespace std;
int const MOD = 1e9 + 7;
int DIV_TWO;
int x11, y11, x22, y22, k;
int sum(int a, int b) { return (a + b) % MOD; }
void add(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  if (a < 0) a += MOD;
}
int mul(int a, int b) { return a * 1LL * b % MOD; }
int bp(int x, int d) {
  if (!d) return 1;
  if (d & 1) return mul(x, bp(x, d - 1));
  int r = bp(x, d / 2);
  return mul(r, r);
}
int asum(int n, int cnt, int add) {
  int f = sum(add, 1);
  int l = sum(add, n);
  int ret = mul(n, sum(f, l));
  ret = mul(ret, DIV_TWO);
  ret = mul(ret, cnt);
  return ret;
}
int max(int a, int b, int c, int d) {
  int max1 = max(a, b);
  int max2 = max(c, d);
  return max(max1, max2);
}
int rec(int s, int w, int h, int k, int addv = 0) {
  if (k <= 0) return 0;
  if (w <= 0 || h <= 0) return 0;
  if (w == s) {
    return asum(min(k, s), h, addv);
  }
  if (h == s) {
    return asum(min(k, s), w, addv);
  }
  int ret = 0;
  int ns = s / 2;
  add(ret, rec(ns, min(ns, w), min(ns, h), k, addv));
  add(ret, rec(ns, w - ns, min(ns, h), k - ns, addv + ns));
  add(ret, rec(ns, min(ns, w), h - ns, k - ns, addv + ns));
  add(ret, rec(ns, w - ns, h - ns, k, addv));
  return ret;
}
int const N = 30;
int ans[N][N];
int get(int col, int row) {
  vector<int> v;
  v.push_back(0);
  for (int i = 1; i < row; ++i) v.push_back(ans[i][col]);
  for (int i = 1; i < col; ++i) v.push_back(ans[row][i]);
  sort(v.begin(), v.end());
  for (int i = 1; i < (int)(v.size()); ++i)
    if (v[i] - v[i - 1] != 1) return v[i - 1] + 1;
  return v.back() + 1;
}
void brute() {
  for (int i = 1; i < N; ++i) {
    for (int j = 1; j < N; ++j) {
      int mini = get(j, i);
      ans[i][j] = mini;
    }
  }
}
int getBrute(int s, int w, int h, int k) {
  int ret = 0;
  for (int y = 1; y < h + 1; ++y)
    for (int x = 1; x < w + 1; ++x)
      if (ans[y][x] <= k) ret += ans[y][x];
  return ret;
}
int solve() {
  cin >> x11 >> y11 >> x22 >> y22 >> k;
  int ans = 0;
  int maxi = max(x11, y11, x22, y22);
  int s = 1;
  while (s < maxi) {
    s *= 2;
  }
  add(ans, rec(s, s, s, k));
  add(ans, -rec(s, s, y11 - 1, k));
  add(ans, -rec(s, x11 - 1, s, k));
  add(ans, -rec(s, s - x22, s, k));
  add(ans, -rec(s, s, s - y22, k));
  add(ans, rec(s, x11 - 1, y11 - 1, k));
  add(ans, rec(s, s, y11 - 1, k));
  add(ans, -rec(s, x22, y11 - 1, k));
  add(ans, rec(s, x11 - 1, s, k));
  add(ans, -rec(s, x11 - 1, y22, k));
  add(ans, rec(s, s, s, k));
  add(ans, -rec(s, x22, s, k));
  add(ans, -rec(s, s, y22, k));
  add(ans, rec(s, x22, y22, k));
  return ans;
}
int main() {
  DIV_TWO = bp(2, MOD - 2);
  int test;
  cin >> test;
  while (test--) {
    cout << solve() << endl;
  }
  return 0;
}
