#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int add(int x, int y) {
  while (x >= mod) x -= mod;
  while (y >= mod) y -= mod;
  x += y;
  while (x >= mod) x -= mod;
  return x;
}
int T, k;
int calc(int, int, long long);
int main() {
  scanf("%d", &T);
  while (T--) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    printf("%d\n", add(add(calc(x2, y2, 0), calc(x1 - 1, y1 - 1, 0)),
                       mod - add(calc(x1 - 1, y2, 0), calc(x2, y1 - 1, 0))));
  }
  return 0;
}
int calc(int x, int y, long long p) {
  if (x == 0 || y == 0) return 0;
  if (p >= k) return 0;
  if (x < y) swap(x, y);
  int a = 1;
  while (a <= x) a <<= 1;
  a >>= 1;
  if (a >= y) {
    long long w = min((long long)k, p + a);
    return add((long long)(w - p) * (p + 1 + w) / 2 % mod * y % mod,
               calc(x - a, y, p + a));
  } else {
    long long w = min(p + a, (long long)k);
    return add((long long)(w - p) * (w + p + 1) / 2 % mod * a % mod,
               add(calc(x - a, a, p + a),
                   add(calc(a, y - a, p + a), calc(x - a, y - a, p))));
  }
}
