#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> dp[32][2][2][2];
long long R, C, K;
pair<long long, long long> getways(int pos, int rcap, int ccap, int kcap) {
  if (pos == -1) return {1, 0};
  auto &ans = dp[pos][rcap][ccap][kcap];
  if (ans.first != -1) return ans;
  int rbit = ((R >> pos) & 1);
  int cbit = ((C >> pos) & 1);
  int kbit = ((K >> pos) & 1);
  ans = getways(pos - 1, (rcap & (rbit == 0)), (ccap & (cbit == 0)),
                (kcap & (kbit == 0)));
  if ((ccap == 0 || cbit == 1) && (kcap == 0 || kbit == 1)) {
    auto cways = getways(pos - 1, (rcap & (rbit == 0)), ccap, kcap);
    ans.first += cways.first;
    ans.second += cways.second + (((1LL << pos) * cways.first) % 1000000007);
  }
  if ((rcap == 0 || rbit == 1) && (kcap == 0 || kbit == 1)) {
    auto cways = getways(pos - 1, rcap, (ccap & (cbit == 0)), kcap);
    ans.first += cways.first;
    ans.second += cways.second + (((1LL << pos) * cways.first) % 1000000007);
  }
  if ((rcap == 0 || rbit == 1) && (ccap == 0 || cbit == 1)) {
    auto cways = getways(pos - 1, rcap, ccap, (kcap & (kbit == 0)));
    ans.first += cways.first;
    ans.second += cways.second;
  }
  ans.first %= 1000000007;
  ans.second %= 1000000007;
  return ans;
}
long long getsum(long long x, long long y, long long k) {
  if (x < 0 || y < 0) return 0;
  for (int i = 0; i < 32; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        for (int l = 0; l < 2; l++) {
          dp[i][j][k][l].first = -1;
        }
      }
    }
  }
  R = x;
  C = y;
  K = k;
  auto ret = getways(31, 1, 1, 1);
  return (ret.first + ret.second) % 1000000007;
}
int main() {
  int q;
  int x1, y1, x2, y2, k;
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &k);
    k--;
    x1--;
    x2--;
    y1--;
    y2--;
    printf("%Ld\n",
           (getsum(x2, y2, k) + 1000000007 - getsum(x1 - 1, y2, k) +
            1000000007 - getsum(x2, y1 - 1, k) + getsum(x1 - 1, y1 - 1, k)) %
               1000000007);
  }
  return 0;
}
