#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char c = getchar();
  int p = 1, ret = 0;
  while ((c < '0') || (c > '9')) {
    if (c == '-') p = -1;
    c = getchar();
  }
  while ((c >= '0') && (c <= '9'))
    ret = (ret << 1) + (ret << 3) + c - '0', c = getchar();
  return ret * p;
}
int n;
int dp[32][2][2][2], Dp[32][2][2][2];
int a[31], b[31], c[31];
void add(int &x, int y) { x = (x + y) % 1000000007; }
inline long long query(int x, int y, int k) {
  if (x < 0 || (y < 0)) return 0;
  for (int i = 0; i < 31; i++)
    a[i] = x >> i & 1, b[i] = y >> i & 1, c[i] = k >> i & 1;
  dp[31][1][1][1] = 1;
  Dp[31][1][1][1] = 0;
  for (int i = 0; i < 31; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        for (int l = 0; l < 2; l++) dp[i][j][k][l] = Dp[i][j][k][l] = 0;
  for (int i = 30; i >= 0; i--)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        for (int l = 0; l < 2; l++)
          for (int p = 0; p < 2; p++)
            for (int q = 0; q < 2; q++) {
              int v = p ^ q;
              if ((j) && (a[i] == 0) && (p)) continue;
              if ((k) && (b[i] == 0) && (q)) continue;
              if ((l) && (c[i] == 0) && (v)) continue;
              add(dp[i][j & (p >= a[i])][k & (q >= b[i])][l & (v >= c[i])],
                  dp[i + 1][j][k][l]);
              add(Dp[i][j & (p >= a[i])][k & (q >= b[i])][l & (v >= c[i])],
                  Dp[i + 1][j][k][l]);
              if (v)
                add(Dp[i][j & (p >= a[i])][k & (q >= b[i])][l & (v >= c[i])],
                    1LL * (1 << i) * dp[i + 1][j][k][l] % 1000000007);
            }
  int ans = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        add(ans, Dp[0][i][j][k]), add(ans, dp[0][i][j][k]);
  return ans;
}
int main() {
  n = read();
  while (n--) {
    int x0 = read() - 2, y0 = read() - 2, x1 = read() - 1, y1 = read() - 1,
        k = read() - 1;
    int ans = 0;
    add(ans, query(x1, y1, k));
    add(ans, -query(x0, y1, k));
    add(ans, -query(x1, y0, k));
    add(ans, query(x0, y0, k));
    if (ans < 0) ans += 1000000007;
    printf("%d\n", ans);
  }
}
