#include <bits/stdc++.h>
using namespace std;
inline long long add(long long x, long long y) {
  return x + y >= ((long long)1e9 + 7) ? x + y - ((long long)1e9 + 7) : x + y;
}
inline long long mns(long long x, long long y) {
  return x - y < 0 ? x - y + ((long long)1e9 + 7) : x - y;
}
struct data {
  long long sum, cnt;
  data() {}
  data(long long ss, long long cc) { sum = ss, cnt = cc; }
};
int vis[35][2][2][2];
data f[35][2][2][2];
int A[35], B[35], C[35];
data dfs(int len, int p1, int p2, int p3) {
  if (!len) {
    return data(0, 1);
  }
  if (vis[len][p1][p2][p3]) {
    return f[len][p1][p2][p3];
  }
  data ans = data(0, 0);
  int r1 = p1 ? A[len] : 1, r2 = p2 ? B[len] : 1, r3 = p3 ? C[len] : 1;
  for (int i = 0; i <= r1; i++) {
    for (int j = 0; j <= r2; j++) {
      if ((i ^ j) <= r3) {
        data tmp = dfs(len - 1, (p1 & (i == A[len])), (p2 & (j == B[len])),
                       (p3 & ((i ^ j) == C[len])));
        ans.cnt = add(ans.cnt, tmp.cnt);
        ans.sum = add(ans.sum, add(tmp.sum, 1LL * (i ^ j) * (1LL << (len - 1)) %
                                                ((long long)1e9 + 7) * tmp.cnt %
                                                ((long long)1e9 + 7)));
      }
    }
  }
  vis[len][p1][p2][p3] = 1;
  f[len][p1][p2][p3] = ans;
  return ans;
}
int get(int a[], long long x) {
  int cnt = 0;
  while (x) {
    a[++cnt] = (x & 1);
    x /= 2;
  }
  return cnt;
}
long long cal(long long x, long long y, long long K) {
  if (x < 0 || y < 0 || K < 0) {
    return 0;
  }
  memset(A, 0, sizeof(A));
  memset(B, 0, sizeof(B));
  memset(C, 0, sizeof(C));
  memset(vis, 0, sizeof(vis));
  int cnta = get(A, x), cntb = get(B, y), cntc = get(C, K);
  data ans = dfs(max(cnta, max(cntb, cntc)), 1, 1, 1);
  return add(ans.sum, ans.cnt);
}
int main() {
  int Task;
  {
    Task = 0;
    char ch;
    int f = 0;
    do {
      ch = getchar();
      if (ch == '-') {
        f = 1;
      }
    } while (ch < '0' || ch > '9');
    while ('0' <= ch && ch <= '9') {
      Task = (Task << 1) + (Task << 3) + ch - 48;
      ch = getchar();
    }
    if (f) Task = -Task;
  }
  long long X1, X2, Y1, Y2, K;
  while (Task--) {
    {
      X1 = 0;
      char ch;
      int f = 0;
      do {
        ch = getchar();
        if (ch == '-') {
          f = 1;
        }
      } while (ch < '0' || ch > '9');
      while ('0' <= ch && ch <= '9') {
        X1 = (X1 << 1) + (X1 << 3) + ch - 48;
        ch = getchar();
      }
      if (f) X1 = -X1;
    }
    {
      Y1 = 0;
      char ch;
      int f = 0;
      do {
        ch = getchar();
        if (ch == '-') {
          f = 1;
        }
      } while (ch < '0' || ch > '9');
      while ('0' <= ch && ch <= '9') {
        Y1 = (Y1 << 1) + (Y1 << 3) + ch - 48;
        ch = getchar();
      }
      if (f) Y1 = -Y1;
    }
    {
      X2 = 0;
      char ch;
      int f = 0;
      do {
        ch = getchar();
        if (ch == '-') {
          f = 1;
        }
      } while (ch < '0' || ch > '9');
      while ('0' <= ch && ch <= '9') {
        X2 = (X2 << 1) + (X2 << 3) + ch - 48;
        ch = getchar();
      }
      if (f) X2 = -X2;
    }
    {
      Y2 = 0;
      char ch;
      int f = 0;
      do {
        ch = getchar();
        if (ch == '-') {
          f = 1;
        }
      } while (ch < '0' || ch > '9');
      while ('0' <= ch && ch <= '9') {
        Y2 = (Y2 << 1) + (Y2 << 3) + ch - 48;
        ch = getchar();
      }
      if (f) Y2 = -Y2;
    }
    {
      K = 0;
      char ch;
      int f = 0;
      do {
        ch = getchar();
        if (ch == '-') {
          f = 1;
        }
      } while (ch < '0' || ch > '9');
      while ('0' <= ch && ch <= '9') {
        K = (K << 1) + (K << 3) + ch - 48;
        ch = getchar();
      }
      if (f) K = -K;
    }
    X1--, X2--, Y1--, Y2--, K--;
    long long t1 = cal(X1 - 1, Y1 - 1, K), t2 = cal(X1 - 1, Y2, K),
              t3 = cal(X2, Y1 - 1, K), t4 = cal(X2, Y2, K);
    printf("%lld\n", mns(add(t1, t4), add(t2, t3)));
  }
  return 0;
}
