#include <bits/stdc++.h>
using namespace std;
int q;
long long int x1;
long long int my1;
long long int x2;
long long int y2;
long long int k;
long long int allowed[32];
long long int width[32];
long long int height[32];
long long int dp[32][2][4];
long long int num[32][2][4];
bool exist[32][2][4];
long long int calc(int x, int y) {
  if (x == 0 || y == 0) return 0;
  int t = max(x, y);
  int cnt = 1;
  while (t > 0) {
    cnt++;
    t /= 2;
  }
  long long int k_ = k;
  int cnt2 = 1;
  while (1) {
    k_ = k_ % 2 ? (k_ + 1) / 2 : k_ / 2;
    cnt2++;
    if (k_ == 1) break;
  }
  cnt = max(cnt, cnt2);
  width[cnt - 1] = x;
  height[cnt - 1] = y;
  allowed[cnt - 1] = k;
  for (int i = cnt - 2; i >= 0; i--) {
    allowed[i] =
        allowed[i + 1] % 2 ? (allowed[i + 1] + 1) / 2 : allowed[i + 1] / 2;
    width[i] = width[i + 1] / 2 + width[i + 1] % 2;
    height[i] = height[i + 1] / 2 + height[i + 1] % 2;
  }
  fill(num[0][0], num[cnt][0], 0);
  fill(dp[0][0], dp[cnt][0], 0);
  fill(exist[0][0], exist[cnt][0], false);
  num[0][1][3] = 1;
  dp[0][1][3] = 1;
  exist[0][1][3] = true;
  for (int i = 0; i < cnt - 1; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 4; k++) {
        if (!exist[i][j][k]) continue;
        for (int s = 0; s < 2; s++) {
          for (int t = 0; t < 2; t++) {
            long long int p = (s + t) % 2;
            long long int v =
                (1000000007 +
                 ((dp[i][j][k] * 2 + (p - 1) * num[i][j][k]) % 1000000007)) %
                1000000007;
            long long int n = num[i][j][k];
            if (j == 1 && p && allowed[i] * 2 > allowed[i + 1]) continue;
            if ((k & 2) && s && width[i] * 2 > width[i + 1]) continue;
            if ((k & 1) && t && height[i] * 2 > height[i + 1]) continue;
            int nj = 0;
            if (j == 1 && allowed[i] * 2 - 1 + p == allowed[i + 1]) nj = 1;
            int nk = 0;
            if ((k & 1) && height[i] * 2 - 1 + t == height[i + 1]) nk += 1;
            if ((k & 2) && width[i] * 2 - 1 + s == width[i + 1]) nk += 2;
            exist[i + 1][nj][nk] = true;
            dp[i + 1][nj][nk] = (dp[i + 1][nj][nk] + v) % 1000000007;
            num[i + 1][nj][nk] = (num[i + 1][nj][nk] + n) % 1000000007;
          }
        }
      }
    }
  }
  long long int ret = 0;
  for (int i = 0; i < 4; i++) {
    ret += dp[cnt - 1][0][i];
    ret += dp[cnt - 1][1][i];
    ret %= 1000000007;
  }
  return ret;
}
int main() {
  scanf("%d", &q);
  while (q--) {
    scanf("%lld%lld%lld%lld%lld", &x1, &my1, &x2, &y2, &k);
    long long int ans = calc(x2, y2) - calc(x2, my1 - 1) - calc(x1 - 1, y2) +
                        calc(x1 - 1, my1 - 1);
    printf("%lld\n", (1000000007 + ans % 1000000007) % 1000000007);
  }
}
