#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int q, k;
int sum(int l, int r) {
  if (l > r) return 0;
  return (long long)(l + r) * (r - l + 1) / 2 % mod;
}
int solve(int x, int y, int h) {
  if (x <= 0 || y <= 0) return 0;
  int mx = max(x, y), t = 1, tmp = 0;
  if (y > x) swap(x, y);
  while (2 * t <= mx) t = 2 * t;
  if (y <= t) {
    tmp += (long long)sum(h + 1, min(k, t + h)) * y % mod;
    tmp %= mod;
    tmp += solve(x - t, y, h + t);
    tmp %= mod;
    return tmp;
  } else {
    tmp += (long long)sum(h + 1, min(k, t + h)) * t % mod;
    tmp %= mod;
    tmp += solve(x - t, y - t, h);
    tmp %= mod;
    tmp += solve(x - t, t, h + t);
    tmp %= mod;
    tmp += solve(t, y - t, h + t);
    tmp %= mod;
    return tmp;
  }
}
int main() {
  scanf("%d", &q);
  while (q--) {
    int x1, x2, y1, y2;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    int ans = solve(x1 - 1, y1 - 1, 0) + solve(x2, y2, 0) -
              solve(x1 - 1, y2, 0) - solve(x2, y1 - 1, 0);
    ans %= mod;
    ans = (ans + mod) % mod;
    printf("%d\n", ans);
  }
  return 0;
}
