#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7, M = 1e9 + 5;
int inx1, iny1, inx2, iny2, k;
bool dInc(int x, int y, int len) {
  int x2 = x + len - 1, y2 = y + len - 1;
  return (x2 < inx1 || x > inx2 || y2 < iny1 || y > iny2);
}
int getSum(unsigned long long x) { return ((x * (x + 1)) / 2) % mod; }
int sum(int len, int start, int len2) {
  int d = start + len - 1;
  d = min(d, k);
  long long S = (getSum(d) - getSum(start - 1)) % mod;
  S = (S + mod) % mod;
  return S * len2 % mod;
}
int solve(int x, int y, int len, int start) {
  if (start > k || dInc(x, y, len)) return 0;
  if (x >= inx1 && x + len - 1 <= inx2)
    return sum(len, start, max(0, min(y + len - 1, iny2) - max(iny1, y) + 1));
  if (y >= iny1 && y + len - 1 <= iny2)
    return sum(len, start, max(0, min(x + len - 1, inx2) - max(inx1, x) + 1));
  long long ret = 0;
  int n_x, n_y;
  n_x = x, n_y = y;
  int n_len = len >> 1;
  ret += solve(n_x, n_y, n_len, start);
  n_x = x, n_y = y + n_len;
  ret += solve(n_x, n_y, n_len, start + n_len);
  n_x = x + n_len, n_y = y;
  ret += solve(n_x, n_y, n_len, start + n_len);
  n_x = x + n_len, n_y = y + n_len;
  ret += solve(n_x, n_y, n_len, start);
  ret %= mod;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int q;
  cin >> q;
  while (q--) {
    cin >> inx1 >> iny1 >> inx2 >> iny2 >> k;
    cout << solve(1, 1, (1 << 30), 1) << "\n";
  }
}
