#include <bits/stdc++.h>
using namespace std;
inline int readInt() {
  static int n, ch;
  n = 0, ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
  return n;
}
const int MAX_N = 200 + 3, MOD = 1e9 + 7;
int n;
long long a[MAX_N][MAX_N];
int mex(int i, int j) {
  static bool vis[MAX_N * 2];
  memset(vis, 0, sizeof vis);
  for (int k = 1; k < i; ++k) vis[a[k][j]] = true;
  for (int k = 1; k < j; ++k) vis[a[i][k]] = true;
  for (int k = 1; k < MAX_N * 2; ++k)
    if (!vis[k]) return k;
}
void printBit(int x) {
  for (int i = 15; i >= 0; --i) printf("%d", x >> i & 1);
  cout << endl;
}
pair<long long, long long> operator+(const pair<long long, long long> &lhs,
                                     const pair<long long, long long> &rhs) {
  return make_pair((lhs.first + rhs.first) % MOD,
                   (lhs.second + rhs.second) % MOD);
}
pair<long long, long long> operator-(const pair<long long, long long> &lhs,
                                     const pair<long long, long long> &rhs) {
  return make_pair((lhs.first - rhs.first + MOD) % MOD,
                   (lhs.second - rhs.second + MOD) % MOD);
}
pair<long long, long long> operator*(const pair<long long, long long> &lhs,
                                     const int &x) {
  return make_pair((lhs.first + lhs.second * x % MOD) % MOD, lhs.second);
}
pair<long long, long long> operator^(const pair<long long, long long> &lhs,
                                     const int &x) {
  return make_pair(lhs.first * x % MOD, lhs.second * x % MOD);
}
pair<long long, long long> calc2(long long n, long long k,
                                 long long start = 1) {
  if (k < start) return make_pair(0, 0);
  k = min(k, n + start - 1);
  return make_pair((k + start) * (k - start + 1) / 2 % MOD,
                   (k - start + 1) % MOD);
}
pair<long long, long long> calc(long long n, long long k) {
  return calc2(n, k) ^ n;
}
pair<long long, long long> solve(int x, int y, int k) {
  if (x <= 0 || y <= 0 || k <= 0) return make_pair(0, 0);
  if (x == 1 && y == 1) return k >= 1 ? make_pair(1, 1) : make_pair(0, 0);
  if (x < y) swap(x, y);
  int logX = ceil(log2(x)), n = 1 << logX, halfN = 1 << (logX - 1);
  if (y <= halfN) {
    return (calc2(halfN, k) ^ y) + solve(x - halfN, y, k - halfN) * halfN;
  } else {
    return calc(halfN, k) +
           (calc2(halfN, k, halfN + 1) ^ (x - halfN + y - halfN)) +
           solve(x - halfN, y - halfN, k);
  }
}
int main() {
  int q = readInt();
  while (q--) {
    int x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt(),
        k = readInt();
    pair<long long, long long> ans = solve(x2, y2, k) - solve(x2, y1 - 1, k) -
                                     solve(x1 - 1, y2, k) +
                                     solve(x1 - 1, y1 - 1, k);
    cout << ans.first << endl;
  }
  return 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) printf("%4d", a[i][j]);
    cout << endl;
  }
  puts("---------------");
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) printf("%4d", ((i - 1) ^ (j - 1)) + 1);
    cout << endl;
  }
  return 0;
  for (int k = 1; k <= 16; ++k) {
    puts(
        "----------------------------------------------------------------------"
        "---");
    printf("%d ", k);
    printBit(k);
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (a[i][j] == k)
          printf("x ");
        else
          printf("  ");
      }
      cout << endl;
    }
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (a[i][j] == k)
          cout << i << ' ' << j << ' ' << (i ^ j ^ abs(i - j)) << endl;
  }
  return 0;
}
