#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;
long long su(long long a) { return a * (a + 1) / 2 % M; }
long long inter(long long a, long long b, long long k) {
  long long start = max(a, min(k, b));
  return (su(start) - su(a) + M) % M;
}
long long elem(long long x, long long y, long long lx, long long ly,
               long long k) {
  long long l = max(lx, ly), occ = min(lx, ly);
  long long b = x ^ y;
  b &= ~(l - 1);
  long long ans = occ * inter(b, b + l, k) % M;
  return ans;
}
long long comp2(long long x, long long ey, long long ly, long long k) {
  long long sum = 0;
  while (x) {
    long long ls1 = x & -x;
    sum += elem(x - ls1, ey, ls1, ly, k);
    x -= ls1;
  }
  return sum % M;
}
long long comp(long long x, long long y, long long k) {
  long long sum = 0;
  while (y) {
    long long ls1 = y & -y;
    sum += comp2(x, y - ls1, ls1, k);
    y -= ls1;
  }
  return sum % M;
}
long long comp(long long x1, long long x2, long long y1, long long y2,
               long long k) {
  return (comp(x2, y2, k) - comp(x1, y2, k) - comp(x2, y1, k) +
          comp(x1, y1, k) + 2 * M) %
         M;
}
signed main() {
  long long q;
  cin >> q;
  for (long long i = 0; i < (long long)(q); i++) {
    long long a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;
    cout << comp(a - 1, c, b - 1, d, k) << endl;
  }
}
