#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
inline bool umin(T1& x, const T2& y) {
  return x > y ? x = y, true : false;
}
template <typename T1, typename T2>
inline bool umax(T1& x, const T2& y) {
  return x < y ? x = y, true : false;
}
const int N = (int)1e6 + 7;
const int mod = (int)1e9 + 7;
const int INF = (int)1e9 + 17;
const long long LLINF = (long long)1e18 + 17;
inline void add(int& x, int y) { x = (0ll + x + y) % mod; }
inline int kbit(int n, int k) { return (n >> k) & 1; }
const int BITS = 31;
int dp[33][2][2][2];
int cnt[33][2][2][2];
int solve(int n, int m, int k) {
  if (n < 0 || m < 0 || k < 0) return 0;
  memset(dp, 0, sizeof dp);
  memset(cnt, 0, sizeof cnt);
  dp[BITS][1][1][1] = 0;
  cnt[BITS][1][1][1] = 1;
  for (int i = (BITS + 1) - 1; i >= (1); --i) {
    for (int flag1 = (0); flag1 < (2); ++flag1)
      for (int flag2 = (0); flag2 < (2); ++flag2)
        for (int flag3 = (0); flag3 < (2); ++flag3) {
          if (cnt[i][flag1][flag2][flag3] == 0) continue;
          for (int bit1 = (0); bit1 < (2); ++bit1)
            for (int bit2 = (0); bit2 < (2); ++bit2) {
              int new_flag1 = flag1;
              int new_flag2 = flag2;
              int new_flag3 = flag3;
              if (flag1) {
                bool bit = kbit(n, i - 1);
                if (bit < bit1) continue;
                if (bit > bit1) new_flag1 = false;
              }
              if (flag2) {
                bool bit = kbit(m, i - 1);
                if (bit < bit2) continue;
                if (bit > bit2) new_flag2 = false;
              }
              if (flag3) {
                bool bit = kbit(k, i - 1);
                if (bit < (bit1 ^ bit2)) continue;
                if (bit > (bit1 ^ bit2)) new_flag3 = false;
              }
              add(dp[i - 1][new_flag1][new_flag2][new_flag3],
                  dp[i][flag1][flag2][flag3]);
              add(dp[i - 1][new_flag1][new_flag2][new_flag3],
                  cnt[i][flag1][flag2][flag3] * (bit1 ^ bit2) *
                      (1ll << (i - 1)) % mod);
              add(cnt[i - 1][new_flag1][new_flag2][new_flag3],
                  cnt[i][flag1][flag2][flag3]);
            }
        }
  }
  int ret = 0;
  for (int flag1 = (0); flag1 < (2); ++flag1)
    for (int flag2 = (0); flag2 < (2); ++flag2)
      for (int flag3 = (0); flag3 < (2); ++flag3) {
        add(ret, dp[0][flag1][flag2][flag3]);
        add(ret, cnt[0][flag1][flag2][flag3]);
      }
  return ret;
}
int solve(int x, int y, int x2, int y2, int k) {
  --x, --y, --x2, --y2;
  long long ans = solve(x2, y2, k - 1);
  ans = (ans - solve(x - 1, y2, k - 1) + mod) % mod;
  ans = (ans - solve(x2, y - 1, k - 1) + mod) % mod;
  ans = (ans + solve(x - 1, y - 1, k - 1)) % mod;
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int q;
  cin >> q;
  while (q-- > 0) {
    int x, y, x2, y2, k;
    cin >> x >> y >> x2 >> y2 >> k;
    cout << solve(x, y, x2, y2, k) << '\n';
  }
  return 0;
}
