#include <bits/stdc++.h>
template <int MOD>
struct Integral {
  int v_ = 0;
  template <typename T>
  Integral(T v) : v_(norm(v)) {
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;
  template <typename T>
  T norm(T v) const {
    if (v >= MOD) v -= MOD;
    if (v < 0) v += MOD;
    if (v >= MOD || v < 0) v = (v % MOD + MOD) % MOD;
    return v;
  }
  int val() const { return v_; }
  Integral operator+(const Integral& rhs) const {
    return Integral(val() + rhs.val());
  }
  Integral operator-(const Integral& rhs) const {
    return Integral(val() - rhs.val());
  }
  Integral operator*(const Integral& rhs) const {
    return Integral(val() * 1LL * rhs.val());
  }
  Integral operator/(const Integral& rhs) const { return *this * rhs.inv(); }
  Integral& operator+=(const Integral& rhs) { return *this = *this + rhs; }
  Integral& operator-=(const Integral& rhs) { return *this = *this - rhs; }
  Integral& operator*=(const Integral& rhs) { return *this = *this * rhs; }
  Integral& operator/=(const Integral& rhs) { return *this = *this / rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral operator++() {
    v_ = norm(v_ + 1);
    return *this;
  }
  const Integral operator++(int) {
    Integral ret = *this;
    ++(*this);
    return ret;
  }
  const Integral operator--() {
    v_ = norm(v_ - 1);
    return *this;
  }
  const Integral operator--(int) {
    Integral ret = *this;
    --(*this);
    return ret;
  }
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for (; b; b >>= 1, a = a * a % MOD)
      if (b & 1) ret = ret * a % MOD;
    return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};
template <int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("Integral{v=") + std::to_string(v.val()) + "}";
}
template <int MOD>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;
  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;
  template <typename T>
  Integral<MOD> operator()(T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
  }
};
const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;
const int inv2 = (MOD + 1) / 2;
inline int get_bit(int v, int at) { return v >> at & 1; }
using Value = std::pair<Mint, Mint>;
Value operator+(const Value& lhs, const Value& rhs) {
  return std::make_pair(lhs.first + rhs.first, lhs.second + rhs.second);
}
Value& operator+=(Value& lhs, const Value& rhs) { return lhs = lhs + rhs; }
const int kBit = 31;
Value calc_cache[kBit][2][2];
bool calc_vis[kBit][2][2];
Value calc(int at, int a1, int b1, bool sa1, bool sb1) {
  if (at == -1) return std::make_pair(Mint(0), Mint(!sa1 && !sb1));
  if (!sa1 && !sb1) {
    int l = 0, r = (1 << (at + 1)) - 1;
    Mint cnt = Mint(r - l + 1);
    return std::make_pair((Mint(l + r) * (r - l + 1) * inv2) * cnt, cnt * cnt);
  }
  if (calc_vis[at][sa1][sb1]) return calc_cache[at][sa1][sb1];
  calc_vis[at][sa1][sb1] = true;
  Value& ret = calc_cache[at][sa1][sb1];
  ret = std::make_pair(Mint(0), Mint(0));
  for (int a = 0; a < 2; ++a) {
    for (int b = 0; b < 2; ++b) {
      if (sa1 && a > get_bit(a1, at)) continue;
      if (sb1 && b > get_bit(b1, at)) continue;
      Value val = calc(at - 1, a1, b1, sa1 && a == get_bit(a1, at),
                       sb1 && b == get_bit(b1, at));
      ret += val;
      if (a ^ b) ret.first += val.second * Mint(1 << at);
    }
  }
  return ret;
}
Value solve_cache[kBit][2][2];
bool solve_vis[kBit][2][2];
Value solve(int at, int a1, int b1, int k, bool sa1, bool sb1) {
  if (at == -1) return std::make_pair(Mint(0), Mint(0));
  if (solve_vis[at][sa1][sb1]) return solve_cache[at][sa1][sb1];
  solve_vis[at][sa1][sb1] = true;
  Value& ret = solve_cache[at][sa1][sb1];
  ret = std::make_pair(Mint(0), Mint(0));
  for (int a = 0; a < 2; ++a) {
    for (int b = 0; b < 2; ++b) {
      if (sa1 && a > get_bit(a1, at)) continue;
      if (sb1 && b > get_bit(b1, at)) continue;
      if ((a ^ b) > get_bit(k, at)) continue;
      if ((a ^ b) < get_bit(k, at)) {
        ret += calc(at - 1, a1, b1, sa1 && a == get_bit(a1, at),
                    sb1 && b == get_bit(b1, at));
      } else {
        Value val = solve(at - 1, a1, b1, k, sa1 && a == get_bit(a1, at),
                          sb1 && b == get_bit(b1, at));
        ret += val;
        if (a ^ b) ret.first += val.second * Mint(1 << at);
      }
    }
  }
  return ret;
}
Mint work(int a1, int b1, int k) {
  if (a1 <= 0 || b1 <= 0) return 0;
  memset(calc_vis, 0, sizeof(calc_vis));
  memset(solve_vis, 0, sizeof(solve_vis));
  Value val = solve(kBit - 1, a1, b1, k, true, true);
  return val.first + val.second;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int q;
  reader >> q;
  while (q--) {
    int a0, b0, a1, b1, k;
    reader >> a0 >> b0 >> a1 >> b1 >> k;
    Mint result = work(a1, b1, k) - work(a0 - 1, b1, k) - work(a1, b0 - 1, k) +
                  work(a0 - 1, b0 - 1, k);
    printf("%d\n", result.val());
  }
}
