#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
void DBG() { cerr << "]" << '\n'; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << h;
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
const int MOD = (int)1e9 + 7;
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  auto solve = [](int a, int b, int k) {
    if (a < 0 || b < 0 || k < 0) return 0LL;
    int B = 30;
    int64 s[B + 2][2][2][2], c[B + 2][2][2][2];
    memset(s, 0, sizeof(s));
    memset(c, 0, sizeof(c));
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) c[B + 1][i][j][k] = 1;
    for (int i = B; i >= 0; i--) {
      for (int eqA = 0; eqA < 2; eqA++) {
        for (int eqB = 0; eqB < 2; eqB++) {
          for (int eqK = 0; eqK < 2; eqK++) {
            int bitA = a >> (B - i) & 1;
            int bitB = b >> (B - i) & 1;
            int bitK = k >> (B - i) & 1;
            int lA = eqA ? bitA : 1;
            int lB = eqB ? bitB : 1;
            int lK = eqK ? bitK : 1;
            for (int x = 0; x <= lA; x++) {
              for (int y = 0; y <= lB; y++) {
                if ((x ^ y) > lK) continue;
                int neqA = eqA && (x == bitA);
                int neqB = eqB && (y == bitB);
                int neqK = eqK && ((x ^ y) == bitK);
                c[i][eqA][eqB][eqK] += c[i + 1][neqA][neqB][neqK];
                c[i][eqA][eqB][eqK] %= MOD;
                s[i][eqA][eqB][eqK] += s[i + 1][neqA][neqB][neqK];
                s[i][eqA][eqB][eqK] %= MOD;
                int64 v = 1LL * (x ^ y) * (1LL << (B - i)) % MOD;
                s[i][eqA][eqB][eqK] += c[i + 1][neqA][neqB][neqK] * v % MOD;
                s[i][eqA][eqB][eqK] %= MOD;
              }
            }
          }
        }
      }
    }
    return s[0][1][1][1] + c[0][1][1][1];
  };
  int q;
  cin >> q;
  while (q--) {
    int f1, c1, f2, c2, k;
    cin >> f1 >> c1 >> f2 >> c2 >> k;
    f1--, c1--, f2--, c2--, k--;
    int64 ans = solve(f2, c2, k) - solve(f2, c1 - 1, k) - solve(f1 - 1, c2, k) +
                solve(f1 - 1, c1 - 1, k);
    ans = (ans + 10LL * MOD) % MOD;
    cout << ans << '\n';
  }
  return 0;
}
