#include <bits/stdc++.h>
using namespace std;
const int MX = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
long long k;
long long solve(int first, int second, long long f) {
  if (first == 0 || second == 0 || f > k) return 0;
  if (first < second) swap(first, second);
  if (first == (first & -first)) {
    long long l = f, r = min(k, f + first - 1);
    return (l + r) * (r - l + 1) / 2 % mod * second % mod;
  }
  int d = 1;
  long long ret = 0;
  while ((d << 1) < first) d <<= 1;
  if (second <= d) {
    (ret += solve(d, second, f)) %= mod;
    ;
    (ret += solve(first - d, second, f + d)) %= mod;
    ;
  } else {
    (ret += solve(d, d, f)) %= mod;
    ;
    (ret += solve(first - d, d, f + d)) %= mod;
    ;
    (ret += solve(d, second - d, f + d)) %= mod;
    ;
    (ret += solve(first - d, second - d, f)) %= mod;
    ;
  }
  return ret;
}
int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int x1, x2, y1, y2;
    scanf("%d%d%d%d%I64d", &x1, &y1, &x2, &y2, &k);
    long long ans = solve(x2, y2, 1) + solve(x1 - 1, y1 - 1, 1);
    ans -= solve(x1 - 1, y2, 1) + solve(x2, y1 - 1, 1);
    printf("%I64d\n", (ans + 2 * mod) % mod);
  }
  return 0;
}
