#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 33;
const long long MOD = 1000000007;
long long dp[MAX_N][2][2][2];
long long numb[MAX_N][2][2][2];
int query;
int X1, Y1, X2, Y2, k;
vector<int> change(int r) {
  vector<int> res;
  for (int i = 0; i < 31; i++) {
    if ((long long)r & (1LL << (long long)i)) {
      res.push_back(1);
    } else {
      res.push_back(0);
    }
  }
  return res;
}
long long calc(int x, int y) {
  if (x == 0 || y == 0) {
    return 0;
  }
  memset(dp, 0LL, sizeof(dp));
  memset(numb, 0LL, sizeof(numb));
  vector<int> X, Y, K;
  X = change(x - 1);
  Y = change(y - 1);
  K = change(k - 1);
  long long res = 0LL;
  numb[31][1][1][1] = 1;
  for (int i = 31; i >= 1; i--) {
    for (int flagX = 0; flagX <= 1; flagX++) {
      for (int flagY = 0; flagY <= 1; flagY++) {
        for (int flagK = 0; flagK <= 1; flagK++) {
          if (numb[i][flagX][flagY][flagK] == 0) {
            continue;
          }
          for (int b1 = 0; b1 <= 1; b1++) {
            for (int b2 = 0; b2 <= 1; b2++) {
              if ((flagX == 1 && b1 > X[i - 1]) ||
                  (flagY == 1 && b2 > Y[i - 1]) ||
                  (flagK == 1 && ((b1 ^ b2) > K[i - 1]))) {
                continue;
              }
              int nflagX = (flagX == 1 && b1 == X[i - 1]);
              int nflagY = (flagY == 1 && b2 == Y[i - 1]);
              int nflagK = (flagK == 1 && ((b1 ^ b2) == K[i - 1]));
              (numb[i - 1][nflagX][nflagY][nflagK] +=
               numb[i][flagX][flagY][flagK]) %= MOD;
              (dp[i - 1][nflagX][nflagY][nflagK] +=
               ((dp[i][flagX][flagY][flagK] * 2LL) % MOD +
                numb[i][flagX][flagY][flagK] * (b1 ^ b2)) %
               MOD) %= MOD;
            }
          }
        }
      }
    }
  }
  for (int flagX = 0; flagX <= 1; flagX++) {
    for (int flagY = 0; flagY <= 1; flagY++) {
      for (int flagK = 0; flagK <= 1; flagK++) {
        (res += dp[0][flagX][flagY][flagK]) %= MOD;
        (res += numb[0][flagX][flagY][flagK]) %= MOD;
      }
    }
  }
  return res;
}
int main() {
  scanf("%d", &query);
  while (query--) {
    scanf("%d %d %d %d %d", &X1, &Y1, &X2, &Y2, &k);
    long long res = calc(X2, Y2);
    res -= calc(X1 - 1, Y2);
    res -= calc(X2, Y1 - 1);
    (res += 3LL * MOD) %= MOD;
    (res += calc(X1 - 1, Y1 - 1)) %= MOD;
    printf("%I64d\n", res);
  }
  return 0;
}
