#include <bits/stdc++.h>
using namespace std;
int mod_plus(int a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return a;
}
int mod_mul(long long a, long long b) { return (a * b) % 1000000007; }
int pw2[55];
int dp[55][4][4][2], sum[55][4][4][2];
long long X1, X2, Y1, Y2, val;
int solve(int bit, int xst, int yst, int valst) {
  if (bit < 0) {
    sum[bit + 1][xst][yst][valst] = 0;
    return 1;
  }
  int &ret = dp[bit][xst][yst][valst];
  if (ret != -1) return ret;
  ret = 0;
  int &s = sum[bit + 1][xst][yst][valst];
  s = 0;
  int X1bit = !!(X1 & (1ll << bit)), X2bit = !!(X2 & (1ll << bit)),
      Y1bit = !!(Y1 & (1ll << bit)), Y2bit = !!(Y2 & (1ll << bit));
  int xlo = 0, xhi = 1, ylo = 0, yhi = 1;
  int valbit = !!(val & (1ll << bit));
  if (!(xst & 1) && X1bit) xlo++;
  if (!(xst & 2) && !X2bit) xhi--;
  if (!(yst & 1) && Y1bit) ylo++;
  if (!(yst & 2) && !Y2bit) yhi--;
  for (int i = xlo; i <= xhi; i++) {
    for (int j = ylo; j <= yhi; j++) {
      int kval = i ^ j;
      if (!valst && kval > valbit) continue;
      int tmp = solve(bit - 1, xst | (1 * (i > X1bit)) | (2 * (i < X2bit)),
                      yst | (1 * (j > Y1bit)) | (2 * (j < Y2bit)),
                      valst | (kval < valbit));
      int jog = sum[bit][xst | (1 * (i > X1bit)) | (2 * (i < X2bit))]
                   [yst | (1 * (j > Y1bit)) | (2 * (j < Y2bit))]
                   [valst | (kval < valbit)];
      if (kval) s = mod_plus(s, mod_mul(tmp, pw2[bit]));
      ret = mod_plus(ret, tmp);
      s = mod_plus(s, jog);
    }
  }
  return ret;
}
int main() {
  int q;
  pw2[0] = 1;
  for (q = 1; q < 55; q++) pw2[q] = mod_mul(pw2[q - 1], 2);
  scanf("%d", &q);
  while (q--) {
    scanf("%lld%lld%lld%lld%lld", &X1, &Y1, &X2, &Y2, &val);
    X1--;
    X2--;
    Y1--;
    Y2--;
    val--;
    memset(dp, -1, sizeof(dp));
    int ttt = solve(50, 0, 0, 0);
    printf("%d\n", mod_plus(sum[51][0][0][0], ttt));
  }
  return 0;
}
