#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const long long MOD = 1e9 + 7;
pair<long long, long long> dp[33][2][2][2];
int vis[33][2][2][2], vid;
pair<long long, long long> call(long long pos, bool t1, bool t2, bool t3,
                                long long x, long long y, long long k) {
  if (pos == -1) {
    return make_pair(1, 0);
  }
  if (vis[pos][t1][t2][t3] == vid) return dp[pos][t1][t2][t3];
  if (vis[pos][t1][t2][t3] > 0 and t1 == 0 and t2 == 0 and t3 == 0)
    return dp[pos][t1][t2][t3];
  vis[pos][t1][t2][t3] = vid;
  pair<long long, long long> ret = make_pair(0, 0);
  bool h1 = (t1 ? (x & (1LL << pos)) : 1);
  bool h2 = (t2 ? (y & (1LL << pos)) : 1);
  bool h3 = (t3 ? (k & (1LL << pos)) : 1);
  for (long long f = 0; f <= h1; f++) {
    for (long long s = 0; s <= h2; s++) {
      if ((f ^ s) > h3) continue;
      bool newt1 = t1 & (f == h1);
      bool newt2 = t2 & (s == h2);
      bool newt3 = t3 & ((f ^ s) == h3);
      pair<long long, long long> p =
          call(pos - 1, newt1, newt2, newt3, x, y, k);
      ret.first += p.first;
      ret.second += ((f ^ s) * (1 << pos) * p.first) + p.second;
      ret.second %= MOD;
    }
  }
  ret.first %= MOD;
  return dp[pos][t1][t2][t3] = ret;
}
long long solve(long long x, long long y, long long k) {
  if (x == 0 || y == 0) return 0;
  vid++;
  x--;
  y--;
  k--;
  pair<long long, long long> ans = call(30, 1, 1, 1, x, y, k);
  return (ans.second + ans.first) % MOD;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  long long q;
  cin >> q;
  while (q--) {
    long long x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    long long ans = solve(x2, y2, k) - solve(x1 - 1, y2, k) -
                    solve(x2, y1 - 1, k) + solve(x1 - 1, y1 - 1, k);
    ans = (ans % MOD + MOD) % MOD;
    cout << ans << "\n";
  }
}
