#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
pair<int, int> query(int x, int y, int k, int m) {
  if (x < 1 || y < 1 || m < 1 || k < 1) return make_pair(0, 0);
  if (k <= max(x, y)) {
    int a = min(k, min(x, y));
    int b = min(k, m);
    return make_pair((1LL * a * b) % MOD,
                     (1LL * a * ((1LL * b * (b + 1) / 2) % MOD)) % MOD);
  } else if (k > 1) {
    pair<int, int> q1 = query(x, y, k / 2, m),
                   q2 = query(x - k / 2, y, k / 2, m - k / 2),
                   q3 = query(x, y - k / 2, k / 2, m - k / 2),
                   q4 = query(x - k / 2, y - k / 2, k / 2, m);
    return make_pair((0LL + q1.first + q2.first + q3.first + q4.first) % MOD,
                     (0LL + q1.second + q2.second + q3.second + q4.second +
                      1LL * (q2.first + q3.first) * (k / 2)) %
                         MOD);
  }
  return make_pair(0, 0);
}
int main(void) {
  int q;
  cin >> q;
  while (q--) {
    int x1, y1, x2, y2, m;
    cin >> x1 >> y1 >> x2 >> y2 >> m;
    int k = 1;
    while (k <= max(x2, y2)) k *= 2;
    cout << (2LL * MOD + query(x2, y2, k, m).second -
             query(x1 - 1, y2, k, m).second - query(x2, y1 - 1, k, m).second +
             query(x1 - 1, y1 - 1, k, m).second) %
                MOD
         << "\n";
  }
  return 0;
}
