#include <bits/stdc++.h>
using namespace std;
const int B = 27397, MOD = 1e9 + 7;
const int B1 = 33941, MOD1 = 1e9 + 9;
int q, r, s, k;
int memo_cnt[32][2][2][2], memo_sum[32][2][2][2];
inline int add(int a, int b) {
  a += b;
  while (a < 0) a += MOD;
  return a % MOD;
}
inline int mul(const int &a, const int &b) { return (long long)a * b % MOD; }
inline void init() {
  memset(memo_cnt, -1, sizeof memo_cnt);
  memset(memo_sum, -1, sizeof memo_sum);
}
int get_cnt(int bit, bool flag_r, bool flag_s, bool flag_k) {
  int &ref = memo_cnt[bit][flag_r][flag_s][flag_k];
  if (ref != -1) return ref;
  if (bit == 0) return ref = 1;
  bool r_bit = (r & (1 << (bit - 1))) != 0;
  bool s_bit = (s & (1 << (bit - 1))) != 0;
  bool k_bit = (k & (1 << (bit - 1))) != 0;
  ref = 0;
  for (int i = 0; i < 2; ++i) {
    if (flag_r && i > r_bit) continue;
    for (int j = 0; j < 2; ++j) {
      if (flag_s && j > s_bit) continue;
      if (flag_k && (i ^ j) > k_bit) continue;
      ref = add(ref,
                get_cnt(bit - 1, flag_r && (i == r_bit), flag_s && (j == s_bit),
                        flag_k && ((i ^ j) == k_bit)));
    }
  }
  return ref;
}
int get_sum(int bit, bool flag_r, bool flag_s, bool flag_k) {
  int &ref = memo_sum[bit][flag_r][flag_s][flag_k];
  if (ref != -1) return ref;
  if (bit == 0) return ref = 1;
  bool r_bit = (r & (1 << (bit - 1))) != 0;
  bool s_bit = (s & (1 << (bit - 1))) != 0;
  bool k_bit = (k & (1 << (bit - 1))) != 0;
  ref = 0;
  for (int i = 0; i < 2; ++i) {
    if (flag_r && i > r_bit) continue;
    for (int j = 0; j < 2; ++j) {
      if (flag_s && j > s_bit) continue;
      if (flag_k && (i ^ j) > k_bit) continue;
      int cnt = get_cnt(bit - 1, flag_r && (i == r_bit), flag_s && (j == s_bit),
                        flag_k && ((i ^ j) == k_bit));
      if (i ^ j) ref = add(ref, mul(cnt, 1 << (bit - 1)));
      ref = add(ref,
                get_sum(bit - 1, flag_r && (i == r_bit), flag_s && (j == s_bit),
                        flag_k && ((i ^ j) == k_bit)));
    }
  }
  return ref;
}
int pref(int rr, int ss) {
  r = rr;
  s = ss;
  if (r < 0 || s < 0) return 0;
  init();
  return get_sum(31, true, true, true);
}
int solve(int r1, int s1, int r2, int s2) {
  return add(pref(r2, s2), add(pref(r1 - 1, s1 - 1),
                               add(-pref(r2, s1 - 1), -pref(r1 - 1, s2))));
}
int main(void) {
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int r1, s1, r2, s2;
    scanf("%d%d%d%d%d", &r1, &s1, &r2, &s2, &k);
    --r1;
    --r2;
    --s1;
    --s2;
    --k;
    printf("%d\n", solve(r1, s1, r2, s2));
  }
  return 0;
}
