#include <bits/stdc++.h>
using namespace std;
int a[1100][1100], r[258][258][258], s[258][258][258];
map<pair<int, pair<int, int> >, pair<int, int> > mp;
void operator+=(pair<int, int> &p1, pair<int, int> p2) {
  p1.first += p2.first;
  if (p1.first >= 1000000007) p1.first -= 1000000007;
  p1.second += p2.second;
  if (p1.second >= 1000000007) p1.second -= 1000000007;
}
pair<int, int> C(int x, int y, int up, int now) {
  if (x <= 0 || y <= 0 || up <= 0) return (pair<int, int>){0, 0};
  if (x > y) swap(x, y);
  for (; y <= (1 << now) && now; now--)
    ;
  up = min(up, (1 << now) << 1);
  if (y <= 256)
    return (pair<int, int>){s[min(up, 256)][x][y], r[min(up, 256)][x][y]};
  if (mp.count((pair<int, pair<int, int> >){up, (pair<int, int>){x, y}}))
    return mp[(pair<int, pair<int, int> >){up, (pair<int, int>){x, y}}];
  pair<int, int> res = (pair<int, int>){0, 0}, t;
  t = C(min(x, (1 << now)), min(y, (1 << now)), up, now);
  res += t;
  t = C(x - (1 << now), min(y, (1 << now)), up - (1 << now), now);
  t.first = (t.first + (long long)t.second * (1 << now)) % 1000000007;
  res += t;
  t = C(min(x, (1 << now)), y - (1 << now), up - (1 << now), now);
  t.first = (t.first + (long long)t.second * (1 << now)) % 1000000007;
  res += t;
  t = C(x - (1 << now), y - (1 << now), up, now);
  res += t;
  mp[(pair<int, pair<int, int> >){up, (pair<int, int>){x, y}}] = res;
  return res;
}
void mcp(int sz, int x, int y, int ex) {
  for (int i = 1; i <= sz; i++)
    for (int j = 1; j <= sz; j++) a[x + i][y + j] = a[i][j] + ex;
}
int main() {
  a[1][1] = a[2][2] = 1;
  a[1][2] = a[2][1] = 2;
  for (int i = 1; i < 10; i++) {
    mcp(1 << i, 1 << i, 0, 1 << i);
    mcp(1 << i, 0, 1 << i, 1 << i);
    mcp(1 << i, 1 << i, 1 << i, 0);
  }
  memset(s, 0, sizeof s);
  for (int up = 1; up <= 256; up++)
    for (int i = 1; i <= 256; i++)
      for (int j = 1; j <= 256; j++) {
        s[up][i][j] = s[up][i - 1][j] + s[up][i][j - 1] - s[up][i - 1][j - 1] +
                      (a[i][j] > up ? 0 : a[i][j]);
        r[up][i][j] = r[up][i - 1][j] + r[up][i][j - 1] - r[up][i - 1][j - 1] +
                      (a[i][j] > up ? 0 : 1);
      }
  int T, x, xx, y, yy, k;
  for (scanf("%d", &T); T--;) {
    scanf("%d%d%d%d%d", &x, &y, &xx, &yy, &k);
    printf("%I64d\n", ((long long)C(xx, yy, k, 30).first -
                       C(x - 1, yy, k, 30).first - C(xx, y - 1, k, 30).first +
                       C(x - 1, y - 1, k, 30).first + 1000000007 * 233ll) %
                          1000000007);
  }
}
