#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long sum(long long l, long long r) {
  return (l + r) * (r - l + 1) / 2 % mod;
}
int solve(int x1, int x2, int y1, int y2, int k, int p, int add) {
  x1 = max(1, x1);
  x2 = min(x2, (1 << p));
  y1 = max(1, y1);
  y2 = min(y2, (1 << p));
  if (x1 > x2 || y1 > y2) return 0;
  if (x2 - x1 < y2 - y1) return solve(y1, y2, x1, x2, k, p, add);
  if (x1 == 1 && x2 == (1 << p)) {
    long long cnt = (y2 - y1 + 1);
    long long l = add + 1;
    long long r = min((long long)k, (long long)add + (long long)(1 << p));
    if (l > r) return 0;
    return cnt * sum(l, r) % mod;
  }
  int ans = 0, h = (1 << (p - 1));
  ans = (ans + solve(x1, x2, y1, y2, k, p - 1, add)) % mod;
  ans = (ans + solve(x1 - h, x2 - h, y1, y2, k, p - 1, add + h)) % mod;
  ans = (ans + solve(x1, x2, y1 - h, y2 - h, k, p - 1, add + h)) % mod;
  ans = (ans + solve(x1 - h, x2 - h, y1 - h, y2 - h, k, p - 1, add)) % mod;
  return ans;
}
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("%d\n", solve(x1, x2, y1, y2, k, 30, 0));
  }
  return 0;
}
