#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
inline int kpow(long long a, long long b) {
  long long r = 1;
  while (b > 0) {
    if (b & 1) r = r * a % P;
    a = a * a % P, b >>= 1;
  }
  return r;
}
inline void inc(int &x, int y) {
  if ((x += y) >= P) x -= P;
}
int dfs(int x, int y, int k, int dw) {
  if (x <= 0 || y <= 0 || k <= 0) return 0;
  if (x < y) swap(x, y);
  if (x == (x & -x)) {
    int b = min(x, k);
    return 1ll * (dw + 1 + dw + b) * b % P * y % P;
  }
  int t = 1, ret = 0;
  while ((t << 1) < x) t <<= 1;
  if (y <= t) {
    ret = dfs(t, y, k, dw);
    inc(ret, dfs(x - t, y, k - t, dw + t));
  } else {
    ret = dfs(t, t, k, dw);
    inc(ret, dfs(x - t, y - t, k, dw));
    inc(ret, dfs(x - t, t, k - t, dw + t));
    inc(ret, dfs(t, y - t, k - t, dw + t));
  }
  return ret;
}
int main() {
  int q;
  scanf("%d", &q);
  int inv2 = kpow(2, P - 2);
  while (q--) {
    int x1, y1, x2, y2, k;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    int ans = 0;
    inc(ans, (dfs(x2, y2, k, 0) + dfs(x1 - 1, y1 - 1, k, 0)) % P);
    inc(ans, P - dfs(x2, y1 - 1, k, 0));
    inc(ans, P - dfs(x1 - 1, y2, k, 0));
    ans = 1ll * ans * inv2 % P;
    printf("%d\n", ans);
  }
  return 0;
}
