#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 35;
const long long MOD = 1000000007LL;
long long dp[MAX_N][2][2][2][2];
int query, k;
int a[MAX_N], b[MAX_N], c[MAX_N];
void inc(long long &X, long long val) { (X += val) %= MOD; }
long long calc(int x, int y) {
  if (x == 0 || y == 0) {
    return 0LL;
  }
  long long res = 0LL;
  memset(dp, 0, sizeof(dp));
  int xx = x - 1;
  int yy = y - 1;
  int kk = k - 1;
  for (int i = 0; i < 32; i++) {
    a[i] = xx >> i & 1;
    b[i] = yy >> i & 1;
    c[i] = kk >> i & 1;
  }
  dp[31][1][1][1][1] = 1;
  for (int i = 31; i >= 1; i--) {
    for (int flagX = 0; flagX < 2; flagX++) {
      for (int flagY = 0; flagY < 2; flagY++) {
        for (int flagK = 0; flagK < 2; flagK++) {
          if (dp[i][flagX][flagY][flagK][1] > 0) {
            for (int f1 = 0; f1 < 2; f1++)
              for (int f2 = 0; f2 < 2; f2++) {
                if (flagX == 1 && f1 > a[i - 1] ||
                    flagY == 1 && f2 > b[i - 1] ||
                    flagK == 1 && ((f1 ^ f2) > c[i - 1])) {
                  continue;
                }
                inc(dp[i - 1][flagX == 1 && f1 == a[i - 1]]
                      [flagY == 1 && f2 == b[i - 1]]
                      [flagK == 1 && ((f1 ^ f2) == c[i - 1])][1],
                    dp[i][flagX][flagY][flagK][1]);
                inc(dp[i - 1][flagX == 1 && f1 == a[i - 1]]
                      [flagY == 1 && f2 == b[i - 1]]
                      [flagK == 1 && ((f1 ^ f2) == c[i - 1])][0],
                    (dp[i][flagX][flagY][flagK][0] * 2ll +
                     dp[i][flagX][flagY][flagK][1] * (f1 ^ f2)) %
                        MOD);
              }
          }
        }
      }
    }
  }
  for (int flagX = 0; flagX < 2; flagX++) {
    for (int flagY = 0; flagY < 2; flagY++) {
      for (int flagK = 0; flagK < 2; flagK++) {
        (res +=
         dp[0][flagX][flagY][flagK][0] + dp[0][flagX][flagY][flagK][1]) %= MOD;
      }
    }
  }
  return res;
}
int main() {
  scanf("%d", &query);
  while (query--) {
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    scanf("%d", &k);
    printf("%I64d\n", (calc(x2, y2) - calc(x1 - 1, y2) - calc(x2, y1 - 1) +
                       calc(x1 - 1, y1 - 1) + 2LL * MOD) %
                          MOD);
  }
  return 0;
}
