#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
long long dp[32][2][2][2], cnt[32][2][2][2];
bool check[32][2][2][2];
void go(int pos, int flagX, int flagY, int flagK, int first, int second,
        int k) {
  int new_pos = pos - 1;
  bool _x = ((first >> new_pos) & 1);
  bool _y = ((second >> new_pos) & 1);
  bool _k = ((k >> new_pos) & 1);
  bool new_flagX, new_flagY, new_flagK;
  for (int digitX = 0; digitX < 2; digitX++) {
    if (flagX && digitX > _x) continue;
    for (int digitY = 0; digitY < 2; digitY++) {
      if (flagY && digitY > _y) continue;
      if (flagK && (digitX ^ digitY) > _k) continue;
      new_flagX = new_flagY = new_flagK = 0;
      if (flagX && digitX == _x) new_flagX = 1;
      if (flagY && digitY == _y) new_flagY = 1;
      if (flagK && (digitX ^ digitY) == _k) new_flagK = 1;
      check[new_pos][new_flagX][new_flagY][new_flagK] |=
          check[pos][flagX][flagY][flagK];
      cnt[new_pos][new_flagX][new_flagY][new_flagK] +=
          cnt[pos][flagX][flagY][flagK];
      cnt[new_pos][new_flagX][new_flagY][new_flagK] %= MOD;
      int foo = ((int)(digitX ^ digitY) << new_pos) % MOD;
      dp[new_pos][new_flagX][new_flagY][new_flagK] +=
          dp[pos][flagX][flagY][flagK] + foo * cnt[pos][flagX][flagY][flagK];
      dp[new_pos][new_flagX][new_flagY][new_flagK] %= MOD;
    }
  }
}
int solve(int first, int second, int k) {
  memset(dp, 0, sizeof(dp));
  memset(cnt, 0, sizeof(cnt));
  memset(check, 0, sizeof(check));
  if (first == 0 || second == 0) return 0;
  first--;
  second--;
  k--;
  cnt[31][1][1][1] = 1;
  check[31][1][1][1] = 1;
  for (int i = 31; i > 0; i--) {
    for (int flagX = 0; flagX < 2; flagX++) {
      for (int flagY = 0; flagY < 2; flagY++) {
        for (int flagK = 0; flagK < 2; flagK++) {
          if (check[i][flagX][flagY][flagK] == 0) continue;
          go(i, flagX, flagY, flagK, first, second, k);
        }
      }
    }
  }
  long long ans = 0;
  for (int flagX = 0; flagX < 2; flagX++) {
    for (int flagY = 0; flagY < 2; flagY++) {
      for (int flagK = 0; flagK < 2; flagK++) {
        ans += dp[0][flagX][flagY][flagK];
        ans += cnt[0][flagX][flagY][flagK];
        ans %= MOD;
      }
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int ntest;
  cin >> ntest;
  while (ntest--) {
    int first, second, xx, yy, k;
    cin >> first >> second >> xx >> yy >> k;
    long long ans = solve(xx, yy, k) - solve(xx, second - 1, k) -
                    solve(first - 1, yy, k) + solve(first - 1, second - 1, k);
    ans %= MOD;
    if (ans < 0) ans += MOD;
    cout << ans << endl;
  }
  return 0;
}
