#include <bits/stdc++.h>
using namespace std;
long long dp[32][2][2][2];
long long sum[32][2][2][2];
const int mod = (int)1e9 + 7;
long long solve(int x, int y, int k) {
  memset(dp, 0, sizeof dp);
  memset(sum, 0, sizeof sum);
  dp[0][1][1][1] = 1;
  vector<int> a, b, c;
  for (int i = 0; i < 31; ++i) {
    a.push_back(x % 2);
    b.push_back(y % 2);
    c.push_back(k % 2);
    x /= 2, y /= 2, k /= 2;
  }
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  reverse(c.begin(), c.end());
  for (int i = 0; i < 31; ++i) {
    for (int fx = 0; fx < 2; ++fx) {
      for (int fy = 0; fy < 2; ++fy) {
        for (int fz = 0; fz < 2; ++fz) {
          for (int xx = 0; xx < 2; ++xx) {
            for (int yy = 0; yy < 2; ++yy) {
              int zz = xx ^ yy;
              if (fx == 1 && xx > a[i]) continue;
              if (fy == 1 && yy > b[i]) continue;
              if (fz == 1 && zz > c[i]) continue;
              dp[i + 1][fx & (xx == a[i])][fy & (yy == b[i])]
                [fz & (zz == c[i])] += dp[i][fx][fy][fz];
              sum[i + 1][fx & (xx == a[i])][fy & (yy == b[i])]
                 [fz & (zz == c[i])] += sum[i][fx][fy][fz];
              if (zz == 1)
                sum[i + 1][fx & (xx == a[i])][fy & (yy == b[i])]
                   [fz & (zz == c[i])] +=
                    dp[i][fx][fy][fz] * 1LL * (1 << (30 - i));
              dp[i + 1][fx & (xx == a[i])][fy & (yy == b[i])]
                [fz & (zz == c[i])] %= mod;
              sum[i + 1][fx & (xx == a[i])][fy & (yy == b[i])]
                 [fz & (zz == c[i])] %= mod;
            }
          }
        }
      }
    }
  }
  return (sum[31][0][0][0] + dp[31][0][0][0]) % mod;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    --x1;
    --x2;
    --y1;
    --y2;
    --k;
    long long result = 0;
    result += solve(x2 + 1, y2 + 1, k + 1);
    result += solve(x1, y1, k + 1);
    result -= solve(x2 + 1, y1, k + 1);
    result -= solve(x1, y2 + 1, k + 1);
    result = (result % mod + mod) % mod;
    cout << result << '\n';
  }
  return 0;
}
