#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> que_row(int y, int lvl, int k) {
  long long top = min(k, (1 << lvl));
  return {(y + 0LL) * (top * (top + 1) / 2 % 1000000007LL) % 1000000007LL,
          (y + 0LL) * top % 1000000007LL};
}
pair<long long, long long> que(int x, int y, int lvl, int k) {
  if (k <= 0 || x <= 0 || y <= 0) return {0, 0};
  if (x == (1 << lvl)) {
    return que_row(y, lvl, k);
  }
  if (y == (1 << lvl)) {
    return que_row(x, lvl, k);
  }
  int mid = 1 << (lvl - 1);
  auto tl = que(min(x, mid), min(y, mid), lvl - 1, k);
  auto tr = que(min(x, mid), y - mid, lvl - 1, k - mid);
  auto bl = que(x - mid, min(y, mid), lvl - 1, k - mid);
  auto br = que(x - mid, y - mid, lvl - 1, k);
  return {(tl.first + tr.first + bl.first + br.first +
           mid * (tr.second + bl.second)) %
              1000000007LL,
          (tl.second + tr.second + bl.second + br.second) % 1000000007LL};
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int x1, y1, x2, y2, k;
    scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &k);
    x1--, y1--;
    long long ans = que(x2, y2, 30, k).first - que(x1, y2, 30, k).first -
                    que(x2, y1, 30, k).first + que(x1, y1, 30, k).first;
    ans %= 1000000007LL;
    if (ans < 0) ans += 1000000007LL;
    printf("%lld\n", ans);
  }
}
