#include <bits/stdc++.h>
const int N = 100;
const int moder = 1e9 + 7;
int power[N];
int test;
int powermod(int a, int exp) {
  int ret = 1;
  for (; exp; exp >>= 1) {
    if (exp & 1) {
      ret = 1ll * ret * a % moder;
    }
    a = 1ll * a * a % moder;
  }
  return ret;
}
int sum(int x) { return 1ll * x * (x + 1) / 2 % moder; }
int solve(int x, int y, int k) {
  if (!x || !y) {
    return 0;
  }
  int ret = 0;
  for (int i = 0; i < 30; ++i) {
    for (int j = 0; j < 30; ++j) {
      if ((x >> i & 1) && (y >> j & 1)) {
        int x1 = (x >> i) - 1, y1 = (y >> j) - 1;
        if (i < j) {
          x1 >>= j - i;
        } else {
          y1 >>= i - j;
        }
        int z1 = x1 ^ y1, z2 = z1, max = std::max(i, j);
        for (int u = 0; u < max; ++u) {
          z1 = z1 << 1;
          z2 = z2 << 1 | 1;
        }
        if (k < z1) {
          continue;
        }
        int kk = std::min(z2, k);
        ret = (ret +
               1ll * power[std::min(i, j)] * (sum(kk) - sum(z1 - 1) + moder)) %
              moder;
        ret =
            (ret + 1ll * power[std::min(i, j)] * (kk - z1 + 1 + moder)) % moder;
      }
    }
  }
  return ret;
}
int main() {
  power[0] = 1;
  for (int i = 1; i < N; ++i) {
    power[i] = 2 * power[i - 1] % moder;
  }
  scanf("%d", &test);
  while (test--) {
    int x1, x2, y1, y2, k;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
    --k;
    int ans = (solve(x2, y2, k) + solve(x1 - 1, y1 - 1, k)) % moder;
    ans = (ans - solve(x2, y1 - 1, k) + moder) % moder;
    ans = (ans - solve(x1 - 1, y2, k) + moder) % moder;
    printf("%d\n", ans);
  }
  return 0;
}
