#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct data {
  int x1, y1, x2, y2, len;
  inline data() {}
  inline data(int _x1, int _y1, int _x2, int _y2)
      : x1(_x1), y1(_y1), x2(_x2), y2(_y2), len(x2 - x1 + 1) {}
  inline data ls() { return data(x1, y1, x2 - len / 2, y2 - len / 2); }
  inline data rs() { return data(x1 + len / 2, y1, x2, y2 - len / 2); }
  inline data ls1() { return data(x1, y1 + len / 2, x2 - len / 2, y2); }
  inline data rs1() { return data(x1 + len / 2, y1 + len / 2, x2, y2); }
  inline data ins(data a) {
    return data(max(x1, a.x1), max(y1, a.y1), min(x2, a.x2), min(y2, a.y2));
  }
  bool check() { return x1 <= x2 && y1 <= y2; }
  int size() { return (long long)(x2 - x1 + 1) * (y2 - y1 + 1) % mod; }
};
inline int get(int x) { return (long long)x * (x + 1) / 2 % mod; }
int solve(data a, data b, int K, int dir) {
  if (K <= 0 || !b.check()) return 0;
  int val = get(min(a.len, K)), d = min(a.len, K);
  if (b.y1 == a.y1 && b.y2 == a.y2) {
    int x = b.x2 - b.x1 + 1;
    return ((long long)val * x % mod + (long long)dir * d % mod * x % mod) %
           mod;
  }
  if (b.x1 == a.x1 && b.x2 == a.x2) {
    int y = b.y2 - b.y1 + 1;
    return ((long long)val * y % mod + (long long)dir * d % mod * y % mod) %
           mod;
  }
  long long ans = 0;
  data temp1, temp2;
  temp1 = a.ls();
  temp2 = temp1.ins(b);
  ans += solve(temp1, temp2, K, dir);
  temp1 = a.rs();
  temp2 = temp1.ins(b);
  ans += solve(temp1, temp2, K - a.len / 2, dir + a.len / 2);
  temp1 = a.ls1();
  temp2 = temp1.ins(b);
  ans += solve(temp1, temp2, K - a.len / 2, dir + a.len / 2);
  temp1 = a.rs1();
  temp2 = temp1.ins(b);
  ans += solve(temp1, temp2, K, dir);
  return ans % mod;
}
int main() {
  int Q;
  cin >> Q;
  while (Q--) {
    int x1, x2, y1, y2, K, len = 0;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &K);
    swap(x1, y1);
    swap(x2, y2);
    for (len = 1; len < x2 || len < y2; len <<= 1)
      ;
    int ans = solve(data(1, 1, len, len), data(x1, y1, x2, y2), K, 0);
    printf("%d\n", ans);
  }
  return 0;
}
