#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
template <typename T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
T LCM(T a, T b) {
  return a * (b / gcd(a, b));
}
template <typename T>
T expo(T base, T e, T mod) {
  T res = 1;
  while (e > 0) {
    if (e & 1) res = res * base % mod;
    base = base * base % mod;
    e >>= 1;
  }
  return res;
}
template <typename T, typename second>
T expo(T b, second e) {
  if (e <= 1) return e == 0 ? 1 : b;
  return (e & 1) == 0 ? expo((b * b), e >> 1) : (b * expo((b * b), e >> 1));
}
template <typename T, typename second>
T modinv(T a, second mod) {
  return expo(a, mod - 2, mod);
}
template <class T, class second>
std::ostream &operator<<(std::ostream &os, const std::pair<T, second> &t) {
  os << "(" << t.first << ", " << t.second << ")";
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &t) {
  os << "[";
  for (__typeof(t.begin()) it = t.begin(); it != t.end(); it++) {
    if (it != t.begin()) os << ", ";
    os << *it;
  }
  os << "]";
  return os;
}
template <typename T>
void in(T &x) {
  T c = getchar();
  while (((c < 48) || (c > 57)) && (c != '-')) c = getchar();
  bool neg = false;
  if (c == '-') neg = true;
  x = 0;
  for (; c < 48 || c > 57; c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) x = (x * 10) + (c - 48);
  if (neg) x = -x;
}
const int BITS = 31;
long long cnt[BITS + 3][2][2][2];
long long dp[BITS + 3][2][2][2];
void compute_cnt(long long r, long long c, long long k) {
  memset(cnt, 0, sizeof cnt);
  memset(dp, 0, sizeof dp);
  cnt[BITS][1][1][1] = 1;
  dp[BITS][1][1][1] = 0;
  for (int bits = BITS; bits > 0; bits--) {
    for (int r_flag = 0; r_flag < 2; r_flag++) {
      for (int c_flag = 0; c_flag < 2; c_flag++) {
        for (int k_flag = 0; k_flag < 2; k_flag++) {
          for (int r_bit = 0; r_bit < 2; r_bit++) {
            for (int c_bit = 0; c_bit < 2; c_bit++) {
              int cr = (r >> (bits - 1)) & 1;
              int cc = (c >> (bits - 1)) & 1;
              int ck = (k >> (bits - 1)) & 1;
              int xb = r_bit ^ c_bit;
              if (r_flag * r_bit > cr || c_flag * c_bit > cc ||
                  k_flag * xb > ck) {
              } else {
                int nr_flag = r_flag & (r_bit == cr);
                int nc_flag = c_flag & (c_bit == cc);
                int nk_flag = k_flag & (xb == ck);
                cnt[bits - 1][nr_flag][nc_flag][nk_flag] +=
                    cnt[bits][r_flag][c_flag][k_flag];
                cnt[bits - 1][nr_flag][nc_flag][nk_flag] %= mod;
                dp[bits - 1][nr_flag][nc_flag][nk_flag] +=
                    dp[bits][r_flag][c_flag][k_flag];
                if (xb == 1) {
                  dp[bits - 1][nr_flag][nc_flag][nk_flag] +=
                      expo(2ll, (long long)bits - 1, mod) *
                      cnt[bits][r_flag][c_flag][k_flag] % mod;
                }
                dp[bits - 1][nr_flag][nc_flag][nk_flag] %= mod;
              }
            }
          }
        }
      }
    }
  }
}
long long solve_prefix(long long r, long long c, long long k) {
  if (r < 0 || c < 0) return 0;
  compute_cnt(r, c, k);
  long long res = 0;
  for (int x = 0; x < 2; x++) {
    for (int y = 0; y < 2; y++) {
      for (int z = 0; z < 2; z++) {
        res += dp[0][x][y][z] + cnt[0][x][y][z];
        if (res >= mod) res -= mod;
      }
    }
  }
  return res;
}
long long solve(long long r1, long long c1, long long r2, long long c2,
                long long k) {
  long long res =
      solve_prefix(r2, c2, k - 1) + solve_prefix(r1 - 1, c1 - 1, k - 1);
  res -= solve_prefix(r1 - 1, c2, k - 1) + solve_prefix(r2, c1 - 1, k - 1);
  res %= mod;
  if (res < 0) res += mod;
  return res;
}
int main() {
  int q;
  long long x1, y1, x2, y2, k;
  in(q);
  for (int i = 0; i < q; i++) {
    in(x1), in(y1), in(x2), in(y2), in(k);
    x1--, y1--, x2--, y2--;
    printf("%lld\n", solve(x1, y1, x2, y2, k));
  }
  return 0;
}
