#include <bits/stdc++.h>
using namespace std;
int psum(long long v) {
  long long ans = (v * (v + 1000000007 - 1)) % 1000000007;
  ans = (ans * 500000004LL) % 1000000007;
  return (int)ans;
}
pair<long long, long long> getDP(int x, int y, int k) {
  if (x == 0 || y == 0 || k == 0) return make_pair(0, 0);
  if (x == 1) {
    int low = min(y, k);
    return make_pair(low, psum(low));
  }
  if (y == 1) {
    int low = min(x, k);
    return make_pair(low, psum(low));
  }
  if (k == 1) {
    int low = min(x, y);
    return make_pair(low, low);
  }
  pair<long long, long long> v1 = getDP((x + 1) / 2, (y + 1) / 2, (k + 1) / 2);
  pair<long long, long long> v2 = getDP(x / 2, (y + 1) / 2, k / 2);
  pair<long long, long long> v3 = getDP((x + 1) / 2, y / 2, k / 2);
  pair<long long, long long> v4 = getDP(x / 2, y / 2, (k + 1) / 2);
  int num = (((long long)v1.first) + ((long long)v2.first) +
             ((long long)v3.first) + ((long long)v4.first)) %
            1000000007;
  int ans = (2LL * v1.second + 1000000007 - v1.first) % 1000000007;
  ans = (ans + 2LL * v4.second + 1000000007 - v4.first) % 1000000007;
  ans = (ans + 2LL * v2.second + 2LL * v3.second) % 1000000007;
  return make_pair(num, ans);
}
int mask[31];
pair<long long, long long> getWays(int x, int y, int k) {
  if (x == 0 || y == 0 || k == 0) return make_pair(0, 0);
  int totNum = 0;
  int totSum = 0;
  for (int t = 0; t < 2; t++) {
    for (int i = 30; i >= 0; i--)
      if (x & (1 << i)) {
        x ^= (1 << i);
        for (int j = i - 1; j >= 0; j--)
          if (y & (1 << j)) {
            y ^= (1 << j);
            if (((x ^ y) >> i) < (k >> i)) {
              long long cnum = ((1LL << i) * (1LL << j)) % 1000000007;
              totNum = (totNum + cnum) % 1000000007;
              totSum = (totSum + (1LL << j) * psum(1LL << i)) % 1000000007;
              totSum = (totSum + (((x ^ y) >> i) << i) * cnum) % 1000000007;
            } else if (((x ^ y) >> i) == (k >> i)) {
              long long lowk = (k & ((1 << i) - 1));
              long long cnum = (lowk * (1LL << j)) % 1000000007;
              totNum = (totNum + cnum) % 1000000007;
              totSum = (totSum + (1LL << j) * psum(lowk)) % 1000000007;
              totSum = (totSum + (((x ^ y) >> i) << i) * cnum) % 1000000007;
            }
            y ^= (1 << j);
          }
        x ^= (1 << i);
      }
    swap(x, y);
  }
  for (int i = 30; i >= 0; i--)
    if (x & (1 << i))
      if (y & (1 << i)) {
        x ^= (1 << i);
        y ^= (1 << i);
        if (((x ^ y) >> i) < (k >> i)) {
          long long cnum = ((1LL << i) * (1LL << i)) % 1000000007;
          totNum = (totNum + cnum) % 1000000007;
          totSum = (totSum + (1LL << i) * psum(1LL << i)) % 1000000007;
          totSum = (totSum + (((x ^ y) >> i) << i) * cnum) % 1000000007;
        } else if (((x ^ y) >> i) == (k >> i)) {
          long long lowk = (k & ((1 << i) - 1));
          long long cnum = (lowk * (1LL << i)) % 1000000007;
          totNum = (totNum + cnum) % 1000000007;
          totSum = (totSum + (1LL << i) * psum(lowk)) % 1000000007;
          totSum = (totSum + (((x ^ y) >> i) << i) * cnum) % 1000000007;
        }
        x ^= (1 << i);
        y ^= (1 << i);
      }
  return make_pair(totNum, (totNum + totSum) % 1000000007);
}
int main() {
  int Q, x1, y1, x2, y2, k;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    int ans = getWays(x2, y2, k).second;
    ans = (ans + 1000000007 - getWays(x2, y1 - 1, k).second) % 1000000007;
    ans = (ans + 1000000007 - getWays(x1 - 1, y2, k).second) % 1000000007;
    ans = (ans + getWays(x1 - 1, y1 - 1, k).second) % 1000000007;
    cout << ans << '\n';
  }
}
