#include <bits/stdc++.h>
using namespace std;
static long long dp[32][2][2][2];
static long long sum[32][2][2][2];
static long long pot[32];
void add(long long &x, long long y) {
  x += y;
  if (x >= (int)(1e9 + 7)) {
    x -= (int)(1e9 + 7);
  }
}
void sub(long long &x, long long y) {
  x -= y;
  if (x < 0) {
    x += (int)(1e9 + 7);
  }
}
long long mul(long long x, long long y) { return x * y % (int)(1e9 + 7); }
long long solve(int x, int y, int z) {
  if (x < 0 || y < 0 || z < 0) {
    return 0;
  }
  memset(dp, 0, sizeof(dp));
  memset(sum, 0, sizeof(sum));
  vector<int> A, B, C;
  for (int i = 0; i < 31; i++) {
    A.push_back(x % 2);
    x /= 2;
    B.push_back(y % 2);
    y /= 2;
    C.push_back(z % 2);
    z /= 2;
  }
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  reverse(C.begin(), C.end());
  dp[0][1][1][1] = 1;
  sum[0][1][1][1] = 0;
  for (int i = 0; i < 31; i++) {
    for (int a = 0; a < 2; a++) {
      for (int b = 0; b < 2; b++) {
        for (int c = 0; c < 2; c++) {
          for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
              int z = x ^ y;
              if (a == 1 && A[i] == 0 && x == 1) {
                continue;
              }
              if (b == 1 && B[i] == 0 && y == 1) {
                continue;
              }
              if (c == 1 && C[i] == 0 && z == 1) {
                continue;
              }
              add(dp[i + 1][a & (A[i] == x)][b & (B[i] == y)][c & (C[i] == z)],
                  dp[i][a][b][c]);
              add(sum[i + 1][a & (A[i] == x)][b & (B[i] == y)][c & (C[i] == z)],
                  sum[i][a][b][c]);
              add(sum[i + 1][a & (A[i] == x)][b & (B[i] == y)][c & (C[i] == z)],
                  mul(z << (30 - i), dp[i][a][b][c]));
            }
          }
        }
      }
    }
  }
  long long res = 0;
  for (int a = 0; a < 2; a++) {
    for (int b = 0; b < 2; b++) {
      for (int c = 0; c < 2; c++) {
        add(res, sum[31][a][b][c]);
        add(res, dp[31][a][b][c]);
      }
    }
  }
  return res;
}
int main(int argc, const char *argv[]) {
  int test_case = 0;
  cin >> test_case;
  for (int test = 0; test < test_case; test++) {
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0, k = 0;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    x1--;
    x2--;
    y1--;
    y2--;
    k--;
    long long res = 0;
    add(res, solve(x2, y2, k));
    sub(res, solve(x2, y1 - 1, k));
    sub(res, solve(x1 - 1, y2, k));
    add(res, solve(x1 - 1, y1 - 1, k));
    cout << res << endl;
  }
  return 0;
}
