#include <bits/stdc++.h>
using namespace std;
int K;
struct square {
  int x1, y1, x2, y2;
  square() {}
  square(int a, int b, int c, int d) {
    x1 = a;
    y1 = b;
    x2 = c;
    y2 = d;
  }
  bool is_valid() {
    if (x1 > x2)
      return false;
    else if (y1 > y2)
      return false;
    else
      return true;
  }
  bool is_equal(square s) {
    return ((x1 == s.x1) && (y1 == s.y1) && (x2 == s.x2) && (y2 == s.y2));
  }
  int x_range() { return x2 - x1 + 1; }
  int y_range() { return y2 - y1 + 1; }
  square apply_bias(int bx, int by) {
    return square(x1 - bx, y1 - by, x2 - bx, y2 - by);
  }
};
int calc_quest(square target, int binary_pivot, int bias) {
  if (!target.is_valid()) return 0;
  if (K <= bias) return 0;
  if (target.x_range() == binary_pivot && target.y_range() == binary_pivot) {
    long long bound = (long long)min(binary_pivot + bias, K);
    long long lbias = (long long)bias;
    long long temp;
    temp = (lbias + 1ll + bound) * (bound - lbias) / 2ll;
    temp %= 1000000007;
    temp *= (long long)binary_pivot;
    temp %= 1000000007;
    return (int)temp;
  }
  if (target.x_range() == binary_pivot) {
    long long bound = (long long)min(binary_pivot + bias, K);
    long long lbias = (long long)bias;
    long long temp;
    temp = (lbias + 1ll + bound) * (bound - lbias) / 2ll;
    temp %= 1000000007;
    temp *= (long long)target.y_range();
    temp %= 1000000007;
    return (int)temp;
  }
  if (target.y_range() == binary_pivot) {
    long long bound = (long long)min(binary_pivot + bias, K);
    long long lbias = (long long)bias;
    long long temp;
    temp = (lbias + 1ll + bound) * (bound - lbias) / 2ll;
    temp %= 1000000007;
    temp *= (long long)target.x_range();
    temp %= 1000000007;
    return (int)temp;
  }
  int ans = 0;
  int new_binary_pivot = binary_pivot / 2;
  int x_bound, y_bound;
  x_bound = min(target.x2, new_binary_pivot);
  y_bound = min(target.y2, new_binary_pivot);
  ans += calc_quest(square(target.x1, target.y1, x_bound, y_bound),
                    new_binary_pivot, bias);
  y_bound = max(target.y1, new_binary_pivot + 1);
  ans += calc_quest(square(target.x1, y_bound, x_bound, target.y2)
                        .apply_bias(0, new_binary_pivot),
                    new_binary_pivot, bias + new_binary_pivot);
  ans %= 1000000007;
  x_bound = max(target.x1, new_binary_pivot + 1);
  ans += calc_quest(square(x_bound, y_bound, target.x2, target.y2)
                        .apply_bias(new_binary_pivot, new_binary_pivot),
                    new_binary_pivot, bias);
  ans %= 1000000007;
  y_bound = min(target.y2, new_binary_pivot);
  ans += calc_quest(square(x_bound, target.y1, target.x2, y_bound)
                        .apply_bias(new_binary_pivot, 0),
                    new_binary_pivot, bias + new_binary_pivot);
  ans %= 1000000007;
  return ans;
}
int main() {
  int Q;
  int x1, y1, x2, y2;
  scanf("%d", &Q);
  for (int i = 0; i < Q; i++) {
    scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &K);
    square target = square(x1, y1, x2, y2);
    int temp = max(x2, y2);
    int bound = 1;
    while (temp > bound) bound <<= 1;
    printf("%d\n", calc_quest(target, bound, 0));
  }
  return 0;
}
