#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
int addMod(int a, int b, int m = MOD) {
  a += b;
  if (m <= a) {
    a -= m;
  }
  return a;
}
int mulMod(int a, int b, int m = MOD) { return a * 1ll * b % m; }
int dp[32][2][2][2], dp2[32][2][2][2];
bool bit(int x, int p) { return x & (1 << p); }
int calc(int n, int m, int k) {
  memset(dp, 0, sizeof dp);
  memset(dp2, 0, sizeof dp2);
  dp[31][0][0][0] = 1;
  for (int i = 30; i >= 0; --i) {
    for (int kl = 0; kl < 2; ++kl) {
      for (int nl = 0; nl < 2; ++nl) {
        for (int ml = 0; ml < 2; ++ml) {
          for (int x = 0; x < 2; ++x) {
            for (int y = 0; y < 2; ++y) {
              if (nl == 0 && x > bit(n, i)) {
                continue;
              }
              if (ml == 0 && y > bit(m, i)) {
                continue;
              }
              int z = (x ^ y);
              if (kl == 0 && z > bit(k, i)) {
                continue;
              }
              int nnl = (nl | (x < bit(n, i)));
              int nml = (ml | (y < bit(m, i)));
              int nkl = (kl | (z < bit(k, i)));
              dp[i][nkl][nnl][nml] =
                  addMod(dp[i][nkl][nnl][nml], dp[i + 1][kl][nl][ml]);
              dp2[i][nkl][nnl][nml] =
                  addMod(dp2[i][nkl][nnl][nml], dp2[i + 1][kl][nl][ml]);
              dp2[i][nkl][nnl][nml] = addMod(
                  dp2[i][nkl][nnl][nml], mulMod(z << i, dp[i + 1][kl][nl][ml]));
            }
          }
        }
      }
    }
  }
  return addMod(dp[0][1][1][1], dp2[0][1][1][1]);
}
void solve() {
  int x1, y1, x2, y2, k;
  scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &k);
  int ans = calc(x2, y2, k);
  ans = addMod(ans, MOD - calc(x1 - 1, y2, k));
  ans = addMod(ans, MOD - calc(x2, y1 - 1, k));
  ans = addMod(ans, calc(x1 - 1, y1 - 1, k));
  printf("%d\n", ans);
}
int main() {
  int tt;
  scanf("%d", &tt);
  while (tt--) {
    solve();
  }
  return 0;
}
