#include <bits/stdc++.h>
using namespace std;
const int maxn = 40;
const long long mod = 1000000007;
long long f[maxn][2][2][2];
long long sum[maxn][2][2][2];
long long solve(int a, int b, int k) {
  if (a < 0 || b < 0 || k < 0) return 0;
  memset(f, 0, sizeof(f));
  memset(sum, 0, sizeof(sum));
  for (int s1 = 0; s1 <= 1; s1++)
    for (int s2 = 0; s2 <= 1; s2++)
      for (int s3 = 0; s3 <= 1; s3++) f[0][s1][s2][s3] = 1;
  for (int i = 1; i <= 31; i++) {
    int dx = (a >> (i - 1)) & 1;
    int dy = (b >> (i - 1)) & 1;
    int dxor = (k >> (i - 1)) & 1;
    for (int s1 = 0; s1 <= 1; s1++) {
      for (int s2 = 0; s2 <= 1; s2++) {
        for (int s3 = 0; s3 <= 1; s3++) {
          for (int x = 0; x <= 1; x++) {
            for (int y = 0; y <= 1; y++) {
              int t = x ^ y;
              if (s1 == 0 && x > dx) continue;
              if (s2 == 0 && y > dy) continue;
              if (s3 == 0 && t > dxor) continue;
              int news1 = s1, news2 = s2, news3 = s3;
              if (dx == 1 && x == 0) news1 = 1;
              if (dy == 1 && y == 0) news2 = 1;
              if (dxor == 1 && t == 0) news3 = 1;
              f[i][s1][s2][s3] += f[i - 1][news1][news2][news3];
              f[i][s1][s2][s3] %= mod;
              sum[i][s1][s2][s3] += (sum[i - 1][news1][news2][news3] +
                                     f[i - 1][news1][news2][news3] *
                                         (((1 << (i - 1)) * t) % mod)) %
                                    mod;
              sum[i][s1][s2][s3] %= mod;
            }
          }
        }
      }
    }
  }
  long long ans = (sum[31][0][0][0] + f[31][0][0][0]) % mod;
  return ans;
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int x0, y0, x1, y1, k;
    scanf("%d%d%d%d%d", &x0, &y0, &x1, &y1, &k);
    x0--;
    y0--;
    x1--;
    y1--;
    k--;
    long long ans =
        (solve(x1, y1, k) - solve(x0 - 1, y1, k) - solve(x1, y0 - 1, k) +
         solve(x0 - 1, y0 - 1, k) + mod + mod) %
        mod;
    printf("%I64d\n", ans);
  }
  return 0;
}
