#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int q, x_1, y_1, x_2, y_2, k, len, a[35], b[35], c[35];
pair<int, int> dp[35][2][2][2];
int Add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int Minus(int a, int b) { return a < b ? a - b + mod : a - b; }
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
  return make_pair(Add(a.first, b.first), Add(a.second, b.second));
}
pair<int, int> dfs(int now, int f1, int f2, int f3) {
  if (now == -1) return make_pair(1, 0);
  if (~dp[now][f1][f2][f3].first) return dp[now][f1][f2][f3];
  pair<int, int> ret = make_pair(0, 0);
  for (int i = 0; i <= (f1 ? a[now] : 1); i++)
    for (int j = 0; j <= (f2 ? b[now] : 1); j++)
      if ((i ^ j) <= (f3 ? c[now] : 1)) {
        pair<int, int> tmp = dfs(now - 1, f1 && i == a[now], f2 && j == b[now],
                                 f3 && (i ^ j) == c[now]);
        ret = ret + tmp;
        if (i ^ j) ret.second = (ret.second + (1ll << now) * tmp.first) % mod;
      }
  dp[now][f1][f2][f3] = ret;
  return ret;
}
int calc(int x, int y, int k) {
  if (x < 0 || y < 0) return 0;
  memset(dp, -1, sizeof(dp));
  len = 0;
  while (x || y || k) {
    a[len] = (x & 1);
    b[len] = (y & 1);
    c[len++] = (k & 1);
    x >>= 1;
    y >>= 1;
    k >>= 1;
  }
  pair<int, int> ret = dfs(len - 1, 1, 1, 1);
  return Add(ret.first, ret.second);
}
int main() {
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d%d%d%d", &x_1, &y_1, &x_2, &y_2, &k);
    printf(
        "%d\n",
        Minus(
            Add(calc(x_2 - 1, y_2 - 1, k - 1), calc(x_1 - 2, y_1 - 2, k - 1)),
            Add(calc(x_1 - 2, y_2 - 1, k - 1), calc(x_2 - 1, y_1 - 2, k - 1))));
  }
  return 0;
}
