#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
using namespace std;
const unsigned _mod = 998244353;
const unsigned mod = 1e9 + 7;
const long long infi = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long long qpow(long long x, long long y, long long m) {
  long long ret = 1;
  while (y) {
    if (y & 1ll) ret = ret * x % m;
    y >>= 1ll;
    x = x * x % m;
  }
  return ret;
}
long long ksm(long long x, long long y) {
  long long ret = 1;
  while (y) {
    if (y & 1ll) ret = ret * x % mod;
    y >>= 1ll;
    x = x * x % mod;
  }
  return ret;
}
long long _gcd(long long x, long long y) { return y ? _gcd(y, x % y) : x; }
long long k, x1, x2, nibuyaozaiyongy1le, y2;
long long work(long long x, long long y, long long p) {
  if (!x || !y || p >= k) return 0;
  if (x < y) swap(x, y);
  long long t = x, jyz;
  for (; t; t -= t & -t) jyz = t;
  t = jyz;
  long long w = min(k, p + t);
  if (t >= y)
    return ((w - p) * (p + w + 1) / 2 % mod * y % mod + work(x - t, y, p + t)) %
           mod;
  else
    return (((w - p) * (p + w + 1) / 2 % mod * t % mod +
             work(x - t, min(y, t), p + t) + work(min(t, x), y - t, p + t) +
             work(x - t, y - t, p)) %
            mod);
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    x1 = read(), nibuyaozaiyongy1le = read(), x2 = read(), y2 = read(),
    k = read();
    cout << (work(x2, y2, 0) + work(x1 - 1, nibuyaozaiyongy1le - 1, 0) -
             work(x1 - 1, y2, 0) - work(x2, nibuyaozaiyongy1le - 1, 0) +
             3 * mod) %
                mod
         << '\n';
  }
  return 0;
}
