#include <bits/stdc++.h>
const long long mod = 1000000007;
using namespace std;
long long f1[32][2][2][2], f2[32][2][2][2], t;
long long dp(long long l, long long r, long long k) {
  if (l < 0 || r < 0) return 0;
  for (long long i = 0; i <= 31; i++)
    for (long long a = 0; a < 2; a++)
      for (long long b = 0; b < 2; b++)
        for (long long c = 0; c < 2; c++) f1[i][a][b][c] = f2[i][a][b][c] = 0;
  f1[31][0][0][0] = 1;
  for (long long i = 30; i >= 0; i--)
    for (long long a = 0; a < 2; a++)
      for (long long b = 0; b < 2; b++)
        for (long long c = 0; c < 2; c++)
          if (f1[i + 1][a][b][c]) {
            for (long long aa = 0; aa < 2; aa++)
              for (long long bb = 0; bb < 2; bb++) {
                if (!a && aa && !(l & (1 << i))) continue;
                if (!b && bb && !(r & (1 << i))) continue;
                if (!c && !(k & (1 << i)) && (aa ^ bb)) continue;
                long long na = a, nb = b, nc = c;
                if (!aa && (l & (1 << i))) na |= 1;
                if (!bb && (r & (1 << i))) nb |= 1;
                if (!(aa ^ bb) && (k & (1 << i))) nc |= 1;
                f1[i][na][nb][nc] =
                    (f1[i][na][nb][nc] + f1[i + 1][a][b][c]) % mod;
                f2[i][na][nb][nc] =
                    (f2[i][na][nb][nc] + f2[i + 1][a][b][c]) % mod;
                if (aa ^ bb)
                  f2[i][na][nb][nc] =
                      (f2[i][na][nb][nc] +
                       1ll * (1 << i) % mod * f1[i + 1][a][b][c] % mod) %
                      mod;
              }
          }
  long long ans = 0;
  for (long long a = 0; a <= 1; a++)
    for (long long b = 0; b <= 1; b++)
      for (long long c = 0; c <= 1; c++)
        ans = (ans + f1[0][a][b][c] + f2[0][a][b][c]) % mod;
  return ans;
}
signed main() {
  scanf("%lld", &t);
  do {
    --t;
    long long x, y, xx, yy, k;
    scanf("%lld%lld%lld%lld%lld", &x, &y, &xx, &yy, &k);
    --x;
    --y;
    --xx;
    --yy;
    --k;
    printf("%lld\n", ((((dp(xx, yy, k) + dp(x - 1, y - 1, k)) % mod -
                        dp(xx, y - 1, k) + mod) %
                           mod -
                       dp(x - 1, yy, k)) %
                          mod +
                      mod) %
                         mod);
  } while (t);
}
