#include <bits/stdc++.h>
using namespace std;
static const int INF = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
template <typename T, typename U>
static void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
static void amax(T &x, U y) {
  if (x < y) x = y;
}
template <int MOD>
struct ModInt {
  static const int Mod = MOD;
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  ModInt(signed long long sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  int get() const { return (int)x; }
  ModInt &operator+=(ModInt that) {
    if ((x += that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    if ((x += MOD - that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (unsigned long long)x * that.x % MOD;
    return *this;
  }
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
pair<ModInt<1000000007>, ModInt<1000000007> > memo[33][2][2][2];
int X, Y;
int K;
pair<ModInt<1000000007>, ModInt<1000000007> > rec(int i, bool xlt, bool ylt,
                                                  bool klt) {
  pair<ModInt<1000000007>, ModInt<1000000007> > &r = memo[i + 1][xlt][ylt][klt];
  if (r.first.x != -1) return r;
  if (i == -1) return r = make_pair(xlt && ylt && klt ? 1 : 0, 0);
  int rx = X >> i & 1;
  int ry = Y >> i & 1;
  int rk = K >> i & 1;
  r = {0, 0};
  for (int(x) = 0; (x) < (int)(2); ++(x))
    for (int(y) = 0; (y) < (int)(2); ++(y)) {
      int k = x ^ y;
      if (!xlt && rx < x) continue;
      if (!ylt && ry < y) continue;
      if (!klt && rk < k) continue;
      auto p = rec(i - 1, xlt || x < rx, ylt || y < ry, klt || k < rk);
      r.first += p.first;
      r.second += p.second + p.first * ((long long)k << i);
    }
  return r;
}
int main() {
  int Q;
  while (~scanf("%d", &Q)) {
    for (int(ii) = 0; (ii) < (int)(Q); ++(ii)) {
      int xL;
      int yL;
      int xR;
      int yR;
      scanf("%d%d%d%d", &xL, &yL, &xR, &yR);
      --xL, --yL;
      scanf("%d", &K);
      ModInt<1000000007> ans;
      for (int(x) = 0; (x) < (int)(2); ++(x))
        for (int(y) = 0; (y) < (int)(2); ++(y)) {
          memset(memo, -1, sizeof(memo));
          X = x == 0 ? xR : xL;
          Y = y == 0 ? yR : yL;
          auto p = rec(31, false, false, false);
          ans += (p.second + p.first) * ((x + y) % 2 == 1 ? -1 : 1);
        }
      printf("%d\n", ans.get());
    }
  }
  return 0;
}
