#include <bits/stdc++.h>
using namespace std;
long long qpow(long long x, long long y) {
  long long e = 1;
  while (y) {
    if (y % 2) e = (e * x) % 1000000007;
    x = x * x % 1000000007;
    y /= 2;
  }
  return e;
}
long long low(long long x) {
  for (long long i = 1; i <= x; i <<= 1) {
    if (i << 1 > x) return i;
  }
}
long long getS(long long x, long long y, long long n) {
  return (y - x + 1) * (x + y) % 1000000007 * qpow(2, 1000000007 - 2) %
         1000000007 * n % 1000000007;
}
long long dfs(long long a, long long b, long long k, long long t) {
  if (a <= 0 || b <= 0 || k <= 0) return 0;
  long long l = min(a, b);
  long long r = max(a, b);
  long long x = low(l);
  long long limit = min(r / x, k / x);
  long long ans = 0;
  if (l == r && l == x) {
    ans = (ans + getS(t + 1, t + min(x, k), x)) % 1000000007;
  } else {
    if (limit % 2 == 0) {
      long long rema = min(r - limit * x, x);
      ans = (ans + dfs(x, rema, k - limit * x, t + limit * x)) % 1000000007;
      ans = (ans + dfs(l - x, rema, k - limit * x - x, t + limit * x + x)) %
            1000000007;
      rema = min(r - limit * x - x, x);
      ans = (ans + dfs(x, rema, k - limit * x - x, t + limit * x + x)) %
            1000000007;
      ans = (ans + dfs(l - x, rema, k - limit * x, t + limit * x)) % 1000000007;
    } else {
      limit--;
      ans = (ans + dfs(x, x, k - limit * x, t + limit * x)) % 1000000007;
      ans = (ans + dfs(l - x, x, k - limit * x - x, t + limit * x + x)) %
            1000000007;
      long long rema = min(r - limit * x - x, x);
      ans = (ans + dfs(x, rema, k - limit * x - x, t + limit * x + x)) %
            1000000007;
      ans = (ans + dfs(l - x, rema, k - limit * x, t + limit * x)) % 1000000007;
    }
    ans = (ans + getS(t + 1, t + limit * x, l)) % 1000000007;
  }
  return ans;
}
int main() {
  int N, x1, x2, y1, y2, k;
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    long long ans = ((dfs(x2, y2, k, 0) - dfs(x1 - 1, y2, k, 0) -
                      dfs(x2, y1 - 1, k, 0) + dfs(x1 - 1, y1 - 1, k, 0)) %
                         1000000007 +
                     1000000007) %
                    1000000007;
    printf("%lld\n", ans);
  }
  return 0;
}
