#include <bits/stdc++.h>
using namespace std;
using namespace placeholders;
template <class T>
void mini(T &l, T r) {
  l = min(l, r);
}
template <class T>
void maxi(T &l, T r) {
  l = max(l, r);
}
template <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, a...);
}
template <class T>
ostream &operator<<(ostream &os, vector<T> v) {
  os << "[";
  for (auto vv : v) os << vv << ",";
  return os << "]";
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> p) {
  return os << "(" << p.first << "," << p.second << ")";
}
using llint = long long;
const int B = 1e9 + 7;
int a[40][40];
llint mem[40], cnt[40];
void add(llint &a, llint b) {
  a = (a + b) % B;
  if (a < 0) a += B;
}
void init() {
  mem[0] = 1;
  cnt[0] = 1;
  for (int i = 1; i < 40; ++i) {
    int c = 1 << (i - 1);
    cnt[i] = cnt[i - 1] * 4 % B;
    add(mem[i], mem[i - 1] * 4 % B + 1ll * c * c % B * c % B * 2 % B);
  }
}
llint calc(llint a, llint b) {
  a %= B, b %= B;
  return ((a + b) * (b - a + 1) / 2) % B;
}
pair<llint, llint> get(int x, int y, int k, int d) {
  llint ret = 0;
  int sz = 1 << d;
  if (x < y) swap(x, y);
  if (x <= 0 || y <= 0 || k <= 0) return make_pair(0, 0);
  if (x >= sz) {
    llint a = min(k, sz);
    llint b = min(y, sz);
    ret = calc(1, a) * b % B;
    ;
    return make_pair(b * calc(1, a) % B, b * a % B);
  }
  if (d == 0) return make_pair(1 <= k, 1 <= k);
  int t = 1 << (d - 1);
  auto t1 = get(x, y, k, d - 1);
  auto t2 = get(x - t, y, k - t, d - 1);
  auto t3 = get(y, y - t, k - t, d - 1);
  auto t4 = get(x - t, y - t, k, d - 1);
  ;
  add(ret, t1.first);
  add(ret, t2.first + t2.second * t % B);
  add(ret, t3.first + t3.second * t % B);
  add(ret, t4.first);
  llint c = 0;
  add(c, t1.second);
  add(c, t2.second);
  add(c, t3.second);
  add(c, t4.second);
  ;
  return make_pair(ret, c);
}
llint go(int x1, int y1, int x2, int y2, int k) {
  llint ret = 0;
  add(ret, get(x2, y2, k, 30).first);
  add(ret, -get(x1 - 1, y2, k, 30).first);
  add(ret, -get(x2, y1 - 1, k, 30).first);
  add(ret, get(x1 - 1, y1 - 1, k, 30).first);
  return ret;
}
void run() {
  init();
  ;
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int x1, y1, x2, y2, k;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    printf("%lld\n", go(x1, y1, x2, y2, k));
  }
}
int main() {
  run();
  return 0;
}
