#include <bits/stdc++.h>
using namespace std;
const long long p = 1e9 + 7;
long long read() {
  long long s = 0;
  char c = getchar(), lc = '+';
  while (c < '0' || '9' < c) lc = c, c = getchar();
  while ('0' <= c && c <= '9') s = s * 10 + c - '0', c = getchar();
  return lc == '-' ? -s : s;
}
void write(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x < 10)
    putchar(x + '0');
  else {
    write(x / 10);
    putchar(x % 10 + '0');
  }
}
void print(long long x, char c = '\n') {
  write(x);
  putchar(c);
}
inline void add(long long &x, long long y) {
  x += y;
  if (x >= p) x -= p;
}
inline long long lowbit(long long x) { return x & -x; }
inline long long calc(long long x1, long long x2, long long y1, long long y2,
                      long long k) {
  if (x2 - x1 < y2 - y1) swap(x1, y1), swap(x2, y2);
  long long tmp = x2 - x1;
  x2 = (x1 = (x1 ^ y1) & ~(tmp - 1)) + tmp;
  x1++;
  x2 = min(x2, k);
  if (x1 > x2 || y1 > y2) return 0;
  return (x1 + x2) * (x2 - x1 + 1) / 2 % p * (y2 - y1) % p;
}
inline long long solve(long long x, long long y, long long k) {
  long long ret = 0;
  for (long long i = x; i; i &= i - 1)
    for (long long j = y; j; j &= j - 1)
      add(ret, calc(i - lowbit(i), i, j - lowbit(j), j, k));
  return ret;
}
signed main() {
  long long q = read();
  while (q--) {
    long long x1 = read(), y1 = read(), x2 = read(), y2 = read(), k = read();
    print((solve(x2, y2, k) - solve(x1 - 1, y2, k) - solve(x2, y1 - 1, k) +
           solve(x1 - 1, y1 - 1, k) + p + p) %
          p);
  }
  return 0;
}
