#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
pair<long long, long long> query(int x, int y, int k) {
  if (x <= 0 || y <= 0) return make_pair(0, 0);
  if (x == 1 || y == 1) {
    long long p =
        ((((((x) > (y)) ? (x) : (y))) < (k)) ? ((((x) > (y)) ? (x) : (y)))
                                             : (k));
    long long ret = (p * (p + 1) / 2) % mod;
    return make_pair(ret, p);
  }
  long long ret = 0, cnt = 0;
  long long l = log2((((x) > (y)) ? (x) : (y))),
            p = ((((1ll << l)) < (k)) ? ((1ll << l)) : (k)),
            m = ((((1ll << l)) < ((((x) < (y)) ? (x) : (y))))
                     ? ((1ll << l))
                     : ((((x) < (y)) ? (x) : (y))));
  pair<long long, long long> rem;
  ret = ((((p * (p + 1)) / 2) % mod) * m) % mod;
  cnt = (p * m) % mod;
  long long r = (((x - (1ll << l)) > (0)) ? (x - (1ll << l)) : (0)),
            c = (((y - (1ll << l)) > (0)) ? (y - (1ll << l)) : (0));
  if ((r != 0 && c != 0) || (r == 0 && c == 0)) {
    p = ((((((k) < ((1ll << (l + 1)))) ? (k) : ((1ll << (l + 1)))) -
           (1ll << l)) > (0))
             ? ((((k) < ((1ll << (l + 1)))) ? (k) : ((1ll << (l + 1)))) -
                (1ll << l))
             : (0));
    ret += (((((p * (p + 1)) / 2) % mod) * r) % mod +
            ((((r * p) % mod) * (1ll << l)) % mod)) %
           mod;
    if (ret >= mod) ret -= mod;
    ret += (((((p * (p + 1)) / 2) % mod) * c) % mod +
            ((((c * p) % mod) * (1ll << l)) % mod)) %
           mod;
    if (ret >= mod) ret -= mod;
    cnt = (cnt + (((r + c) % mod) * p) % mod) % mod;
    rem = query(r, c, k);
    cnt = (cnt + rem.second) % mod;
    ret = (ret + rem.first) % mod;
    return make_pair(ret, cnt);
  }
  if (r == 0) {
    rem = query(x, c, (((k - (1ll << l)) > (0)) ? (k - (1ll << l)) : (0)));
  }
  if (c == 0) {
    rem = query(r, y, (((k - (1ll << l)) > (0)) ? (k - (1ll << l)) : (0)));
  }
  ret += ((rem.second * (1ll << l)) % mod + rem.first) % mod;
  if (ret >= mod) ret -= mod;
  cnt = (cnt + rem.second) % mod;
  return make_pair(ret, cnt);
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int x1, x2, y1, y2, k;
    scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &k);
    printf("%lld\n", (query(x2, y2, k).first - query(x1 - 1, y2, k).first -
                      query(x2, y1 - 1, k).first +
                      query(x1 - 1, y1 - 1, k).first + 2 * mod) %
                         mod);
  }
  return 0;
}
