#include <bits/stdc++.h>
using namespace std;
const int mod = (1e9) + 7;
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void sub(int &x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
int f[33][2][2][2], g[33][2][2][2];
int solve(int X, int Y, int K) {
  X--;
  Y--;
  K--;
  if (X < 0 || Y < 0 || K < 0) return 0;
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  int res = 0;
  for (int i = 0; i <= 32; ++i) {
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k)
        for (int t = 0; t < 2; ++t) {
          if (i == 0) {
            g[i][j][k][t] = 1;
            continue;
          }
          int xi = (X & (1 << (i - 1))) > 0;
          int yi = (Y & (1 << (i - 1))) > 0;
          int ki = (K & (1 << (i - 1))) > 0;
          for (int x = 0; x < 2; ++x)
            for (int y = 0; y < 2; ++y) {
              if (j && x > xi) continue;
              if (k && y > yi) continue;
              int z = x ^ y;
              if (t && z > ki) continue;
              int jj = j;
              if (j && x < xi) jj = 0;
              int kk = k;
              if (k && y < yi) kk = 0;
              int tt = t;
              if (t && z < ki) tt = 0;
              add(f[i][j][k][t], f[i - 1][jj][kk][tt]);
              add(f[i][j][k][t],
                  (1ll << (i - 1)) * z * g[i - 1][jj][kk][tt] % mod);
              add(g[i][j][k][t], g[i - 1][jj][kk][tt]);
            }
        }
  }
  add(res, f[31][1][1][1]);
  add(res, g[31][1][1][1]);
  return res;
}
int main() {
  int q;
  cin >> q;
  for (int _ = 0; _ < q; ++_) {
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    int ret = 0;
    add(ret, solve(x2, y2, k));
    sub(ret, solve(x1 - 1, y2, k));
    sub(ret, solve(x2, y1 - 1, k));
    add(ret, solve(x1 - 1, y1 - 1, k));
    cout << ret << endl;
  }
  return 0;
}
