#include <bits/stdc++.h>
using namespace std;
long long mem[33][2][2][2];
long long mem2[33][2][2][2];
vector<int> x, y, z;
long long go(int ind, int xs, int ys, int zs) {
  if (ind >= 32) {
    mem2[ind][xs][ys][zs] = 0;
    return mem[ind][xs][ys][zs] = 1;
  }
  if (mem[ind][xs][ys][zs] != -1) return mem[ind][xs][ys][zs];
  long long a = ((xs || x[ind]) && (ys || y[ind]))
                    ? go(ind + 1, xs, ys, zs | (z[ind] > 0))
                    : 0;
  long long b =
      go(ind + 1, xs | (x[ind] > 0), ys | (y[ind] > 0), zs | (z[ind] > 0));
  long long c = ((zs || z[ind] > 0) && (ys || y[ind] > 0))
                    ? go(ind + 1, xs | (x[ind] > 0), ys, zs)
                    : 0;
  long long d = ((zs || z[ind] > 0) && (xs || x[ind] > 0))
                    ? go(ind + 1, xs, ys | (y[ind] > 0), zs)
                    : 0;
  mem2[ind][xs][ys][zs] = (((1LL << (31 - ind)) % ((long long)(1e9 + 7))) *
                           ((c + d) % ((long long)(1e9 + 7)))) %
                          ((long long)(1e9 + 7));
  mem2[ind][xs][ys][zs] += ((xs || x[ind]) && (ys || y[ind]))
                               ? mem2[ind + 1][xs][ys][zs | (z[ind] > 0)]
                               : 0;
  mem2[ind][xs][ys][zs] +=
      mem2[ind + 1][xs | (x[ind] > 0)][ys | (y[ind] > 0)][zs | (z[ind] > 0)];
  mem2[ind][xs][ys][zs] += ((zs || z[ind] > 0) && (ys || y[ind] > 0))
                               ? mem2[ind + 1][xs | (x[ind] > 0)][ys][zs]
                               : 0;
  mem2[ind][xs][ys][zs] += ((zs || z[ind] > 0) && (xs || x[ind] > 0))
                               ? mem2[ind + 1][xs][ys | (y[ind] > 0)][zs]
                               : 0;
  mem2[ind][xs][ys][zs] %= ((long long)(1e9 + 7));
  return mem[ind][xs][ys][zs] = (a + b + c + d) % ((long long)(1e9 + 7));
}
long long get(int xa, int ya, int za) {
  if (xa < 0 || ya < 0) return 0;
  int i;
  x.clear();
  y.clear();
  z.clear();
  for (i = 0; i < 32; i++) {
    x.push_back(xa % 2);
    y.push_back(ya % 2);
    z.push_back(za % 2);
    xa /= 2;
    ya /= 2;
    za /= 2;
  }
  reverse(x.begin(), x.end());
  reverse(y.begin(), y.end());
  reverse(z.begin(), z.end());
  memset(mem, -1, sizeof mem);
  memset(mem2, 0, sizeof mem2);
  go(0, 0, 0, 0);
  return (mem2[0][0][0][0] + mem[0][0][0][0]) % ((long long)(1e9 + 7));
}
int main() {
  int q;
  cin >> q;
  while (q--) {
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    x1--;
    y1--;
    x2--;
    y2--;
    k--;
    cout << (get(x2, y2, k) - get(x2, y1 - 1, k) - get(x1 - 1, y2, k) +
             get(x1 - 1, y1 - 1, k) + 2 * ((long long)(1e9 + 7))) %
                ((long long)(1e9 + 7))
         << endl;
  }
  return 0;
}
