#include <bits/stdc++.h>
using namespace std;
long long solve(long long u, long long v, long long k, long long o = 0) {
  if (u > v) swap(u, v);
  if (u < 1 || k < 1) return 0;
  long long p = 1, res = 0;
  while (p * 2 <= v) p *= 2;
  long long tmp = min(p, k);
  if (u <= p) {
    res = ((tmp * (tmp + 1) / 2 % 1000000007LL) * u) % 1000000007LL;
    res = (res + (o * tmp % 1000000007LL) * u % 1000000007LL +
           solve(u, v - p, k - p, o + p)) %
          1000000007LL;
  } else {
    res = ((tmp * (tmp + 1) / 2 % 1000000007LL) * p) % 1000000007LL;
    res = (res + o * tmp % 1000000007LL * p % 1000000007LL) % 1000000007LL;
    res = (res + solve(u - p, v - p, k, o) + solve(p, v - p, k - p, o + p) +
           solve(u - p, p, k - p, o + p)) %
          1000000007LL;
  }
  return res;
}
int main() {
  long long q, a, b, u, v, k;
  ios::sync_with_stdio(0);
  cin >> q;
  while (q--) {
    cin >> a >> b >> u >> v >> k;
    long long res = (solve(u, v, k) + solve(a - 1, b - 1, k)) % 1000000007LL;
    res = (res - solve(a - 1, v, k) - solve(u, b - 1, k) +
           1000000007LL * 1000000007LL) %
          1000000007LL;
    cout << res << endl;
  }
  return 0;
}
