#include <bits/stdc++.h>
using namespace std;
inline long long max(long long a, long long b) { return a > b ? a : b; }
inline long long min(long long a, long long b) { return a < b ? a : b; }
const long long mod = 1000000007;
int d[70][70], vis[70], visn;
long long p2[40];
void init() {
  p2[0] = 1;
  for (int i = 1; i < 40; ++i) p2[i] = p2[i - 1] * 2;
}
long long gl(long long v) { return *lower_bound(p2, p2 + 40, v); }
long long sum(long long v) { return v * (v + 1) / 2 % mod; }
long long calc(int x, int y, int k, long long &rn) {
  rn = 0;
  if (k <= 0) return 0;
  if (x == 0 || y == 0) return 0;
  if (x < y) swap(x, y);
  long long n = gl(x), m;
  if (n == 1) {
    rn = 1;
    return 1;
  }
  long long ret;
  if (y >= n / 2) {
    ret = calc(n - x, n - y, k, m);
    rn = (min(n, k) * n % mod + mod - min(n, k) * (n - x + n - y) % mod + m) %
         mod;
    return (sum(min(n, k)) * n - sum(min(n, k)) * (n - x + n - y) % mod + ret) %
           mod;
  }
  rn = min(n, k) * y % mod;
  if (x == n) return sum(min(n, k)) * y % mod;
  ret = calc(x - n / 2, y, k - n / 2, m);
  rn = (min(n / 2, k) * y % mod + m) % mod;
  return (sum(min(n / 2, k)) * y % mod + ret + m * (n / 2) % mod) % mod;
}
int main() {
  int tc;
  init();
  for (scanf("%d", &tc); tc--;) {
    int x1, y1, x2, y2, k;
    long long m;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k), --x1, --y1;
    printf("%lld\n", (calc(x2, y2, k, m) + mod - calc(x1, y2, k, m) + mod -
                      calc(x2, y1, k, m) + calc(x1, y1, k, m)) %
                         mod);
  }
  return 0;
}
