#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int k = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch <= '9' && ch >= '0') {
    k = k * 10 + ch - 48;
    ch = getchar();
  }
  return k;
}
const int p = 1e9 + 7;
inline int Jia(int x) { return x >= p ? x - p : x; }
inline int Jian(int x) { return x >= 0 ? x : x + p; }
int n, f[32][2][2][2], g[32][2][2][2];
int Calc(int lim1, int lim2, int lim3) {
  if (lim1 < 0 || lim2 < 0) return 0;
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  f[31][1][1][1] = 1;
  for (int i = 30; i >= 0; --i) {
    for (int k1 = 0; k1 <= 1; ++k1) {
      for (int k2 = 0; k2 <= 1; ++k2) {
        for (int k3 = 0; k3 <= 1; ++k3) {
          if (!f[i + 1][k1][k2][k3]) continue;
          for (int s1 = 0; s1 <= 1; ++s1) {
            for (int s2 = 0; s2 <= 1; ++s2) {
              if (k1 && s1 && !(lim1 & (1 << i))) continue;
              if (k2 && s2 && !(lim2 & (1 << i))) continue;
              if (k3 && (s1 ^ s2) && !(lim3 & (1 << i))) continue;
              int n1 = k1, n2 = k2, n3 = k3;
              if (k1 && s1 == ((lim1 >> i) & 1))
                n1 = 1;
              else
                n1 = 0;
              if (k2 && s2 == ((lim2 >> i) & 1))
                n2 = 1;
              else
                n2 = 0;
              if (k3 && (s1 ^ s2) == ((lim3 >> i) & 1))
                n3 = 1;
              else
                n3 = 0;
              f[i][n1][n2][n3] = Jia(f[i][n1][n2][n3] + f[i + 1][k1][k2][k3]);
              g[i][n1][n2][n3] = Jia(g[i][n1][n2][n3] + g[i + 1][k1][k2][k3]);
              if (s1 ^ s2)
                g[i][n1][n2][n3] =
                    Jia(g[i][n1][n2][n3] +
                        1LL * (1 << i) * f[i + 1][k1][k2][k3] % p);
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int k1 = 0; k1 <= 1; ++k1) {
    for (int k2 = 0; k2 <= 1; ++k2) {
      for (int k3 = 0; k3 <= 1; ++k3) {
        ans = Jia(ans + f[0][k1][k2][k3]);
        ans = Jia(ans + g[0][k1][k2][k3]);
      }
    }
  }
  return ans;
}
int main() {
  int T = read();
  while (T--) {
    int x1 = read() - 1, y1 = read() - 1, x2 = read() - 1, y2 = read() - 1,
        K = read() - 1;
    int ans = 0;
    ans = Jia(ans + Calc(x2, y2, K));
    ans = Jian(ans - Calc(x1 - 1, y2, K));
    ans = Jian(ans - Calc(x2, y1 - 1, K));
    ans = Jia(ans + Calc(x1 - 1, y1 - 1, K));
    cout << ans << '\n';
  }
  return 0;
}
