#include <bits/stdc++.h>
using namespace std;
const int inv = 1000000000;
const int minv = -inv;
const long long modref = ((long long)(1e9 + 7));
pair<long long, long long> f(int x, int y, int k) {
  if (k <= 0) return pair<long long, long long>(0ll, 0ll);
  if (x < y) return f(y, x, k);
  if (y == 0) return pair<long long, long long>(0ll, 0ll);
  int p2x = 1;
  while ((p2x << 1) <= x) p2x <<= 1;
  long long ret =
      (((long long)(min(p2x, k))) * ((long long)(min(p2x, k) + 1))) / 2ll;
  ret = ret % modref;
  ret = (ret * ((long long)(min(y, p2x)))) % modref;
  long long nret =
      (((long long)(min(p2x, k))) * ((long long)(min(y, p2x)))) % modref;
  pair<long long, long long> recv;
  long long rec, nrec;
  if (y > p2x) {
    recv = f(x - p2x, p2x, k - p2x);
    rec = recv.first;
    nrec = recv.second;
    ret = (ret + rec) % modref;
    ret = (ret + p2x * nrec) % modref;
    nret = (nret + nrec) % modref;
    recv = f(p2x, y - p2x, k - p2x);
    rec = recv.first;
    nrec = recv.second;
    ret = (ret + rec) % modref;
    ret = (ret + p2x * nrec) % modref;
    nret = (nret + nrec) % modref;
    recv = f(x - p2x, y - p2x, k);
    rec = recv.first;
    nrec = recv.second;
    ret = (ret + rec) % modref;
    nret = (nret + nrec) % modref;
  } else {
    recv = f(x - p2x, y, k - p2x);
    rec = recv.first;
    nrec = recv.second;
    ret = (ret + rec) % modref;
    ret = (ret + p2x * nrec) % modref;
    nret = (nret + nrec) % modref;
  }
  return pair<long long, long long>(ret, nret);
}
int main() {
  int q;
  scanf("%d", &q);
  int x1, y1, x2, y2, k;
  for (int z = 0; z < q; ++z) {
    scanf("%d", &x1);
    scanf("%d", &y1);
    scanf("%d", &x2);
    scanf("%d", &y2);
    scanf("%d", &k);
    long long res = f(x2, y2, k).first;
    res = (res + modref - f(x1 - 1, y2, k).first) % modref;
    res = (res + modref - f(x2, y1 - 1, k).first) % modref;
    res = (res + f(x1 - 1, y1 - 1, k).first) % modref;
    cout << res << "\n";
  }
  return 0;
}
