#include <bits/stdc++.h>
using namespace std;
const long long mo = 1e9 + 7;
long long k;
set<long long> s;
inline long long work(long long x, long long y, long long f) {
  if (x <= 0 || y <= 0 || f > k) return 0;
  if (x < y) swap(x, y);
  if (s.find(x) != s.end()) {
    long long l = f, r = min(f + x - 1, k);
    return ((l + r) * (r - l + 1) / 2) % mo * y % mo;
  }
  long long o = *(--(s.lower_bound(x)));
  long long res = 0;
  res = (res + work(o, min(o, y), f)) % mo;
  res = (res + work(o, y - o, f + o)) % mo;
  res = (res + work(x - o, min(y, o), f + o)) % mo;
  res = (res + work(x - o, y - o, f)) % mo;
  return res;
}
inline void solve() {
  long long x1, y1, x2, y2;
  scanf("%lld%lld%lld%lld%lld", &x1, &y1, &x2, &y2, &k);
  long long o1 = work(x2, y2, 1);
  long long o2 = work(x1 - 1, y2, 1);
  long long o3 = work(x2, y1 - 1, 1);
  long long o4 = work(x1 - 1, y1 - 1, 1);
  printf("%lld\n", ((o1 + o4) % mo - o2 - o3 + mo + mo) % mo);
}
int main() {
  long long o = 1;
  while (o <= 1e9) s.insert(o), o *= 2;
  int T = 1;
  scanf("%d", &T);
  while (T--) solve();
}
