#include <bits/stdc++.h>
using namespace std;
long long int cnt[33][3][3][3], dp[33][3][3][3];
pair<long long int, long long int> solve(long long int pos, long long int fx,
                                         long long int fy, long long int fk,
                                         long long int x, long long int y,
                                         long long int k) {
  if (cnt[pos][fx][fy][fk] != -1)
    return make_pair(cnt[pos][fx][fy][fk], dp[pos][fx][fy][fk]);
  long long int& ct = cnt[pos][fx][fy][fk];
  long long int& sum = dp[pos][fx][fy][fk];
  ct = 0;
  sum = 0;
  if (pos == 1) {
    if (fx == 0 && fy == 0) {
      if (fk == 0) {
        ct = 4;
        sum = 2;
      } else {
        if (k & 1) {
          ct = 2;
          sum = 0;
        }
      }
    } else if (fx == 0) {
      if (y & 1) {
        if (fk == 0) {
          ct = 2;
          sum = 1;
        } else {
          if (k & 1) {
            ct = 1;
            sum = 0;
          }
        }
      }
    } else if (fy == 0) {
      if (x & 1) {
        if (fk == 0) {
          ct = 2;
          sum = 1;
        } else {
          if (k & 1) {
            ct = 1;
            sum = 0;
          }
        }
      }
    } else {
      if ((x & 1) && (y & 1)) {
        if (fk == 0) {
          ct = 1;
          sum = 0;
        } else {
          if (k & 1) {
            ct = 1;
            sum = 0;
          }
        }
      }
    }
    return make_pair(ct, sum);
  }
  long long int vx = x & (1LL << (pos - 1));
  long long int vy = y & (1LL << (pos - 1));
  long long int vk = k & (1LL << (pos - 1));
  vx = !vx;
  vx = !vx;
  vy = !vy;
  vy = !vy;
  vk = !vk;
  vk = !vk;
  for (long long int xbit = 0; xbit <= 1; ++xbit) {
    for (long long int ybit = 0; ybit <= 1; ++ybit) {
      if (fx == 1 && xbit > vx) continue;
      if (fy == 1 && ybit > vy) continue;
      if (fk == 1 && ((xbit ^ ybit) > vk)) continue;
      long long int px = 0;
      if (fx == 1 && xbit == vx) px = 1;
      long long int py = 0;
      if (fy == 1 && ybit == vy) py = 1;
      long long int pk = 0;
      if (fk == 1 && ((xbit ^ ybit) == vk)) pk = 1;
      pair<long long int, long long int> xp1 =
          solve(pos - 1, px, py, pk, x, y, k);
      sum = (sum + xp1.second) % 1000000007;
      ct = (ct + xp1.first) % 1000000007;
      sum = (sum +
             (xp1.first * ((xbit ^ ybit) * (1LL << (pos - 1)))) % 1000000007) %
            1000000007;
    }
  }
  if (pos != 31)
    return make_pair(ct, sum);
  else
    return (make_pair(ct, (ct + sum) % 1000000007));
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long int q;
  cin >> q;
  while (q--) {
    long long int x1, y1, x2, y2, kk;
    cin >> x1 >> y1 >> x2 >> y2 >> kk;
    for (long long int i = 0; i <= 32; ++i)
      for (long long int j = 0; j <= 2; ++j)
        for (long long int k = 0; k <= 2; ++k)
          for (long long int l = 0; l <= 2; ++l)
            dp[i][j][k][l] = 0, cnt[i][j][k][l] = -1;
    long long int ans = solve(31, 1, 1, 1, x2, y2, kk).second;
    for (long long int i = 0; i <= 32; ++i)
      for (long long int j = 0; j <= 2; ++j)
        for (long long int k = 0; k <= 2; ++k)
          for (long long int l = 0; l <= 2; ++l)
            dp[i][j][k][l] = 0, cnt[i][j][k][l] = -1;
    if (x1 != 1)
      ans = ((ans - solve(31, 1, 1, 1, x1 - 1, y2, kk).second) % 1000000007 +
             1000000007) %
            1000000007;
    for (long long int i = 0; i <= 32; ++i)
      for (long long int j = 0; j <= 2; ++j)
        for (long long int k = 0; k <= 2; ++k)
          for (long long int l = 0; l <= 2; ++l)
            dp[i][j][k][l] = 0, cnt[i][j][k][l] = -1;
    if (y1 != 1)
      ans = ((ans - solve(31, 1, 1, 1, x2, y1 - 1, kk).second) % 1000000007 +
             1000000007) %
            1000000007;
    for (long long int i = 0; i <= 32; ++i)
      for (long long int j = 0; j <= 2; ++j)
        for (long long int k = 0; k <= 2; ++k)
          for (long long int l = 0; l <= 2; ++l)
            dp[i][j][k][l] = 0, cnt[i][j][k][l] = -1;
    if (y1 != 1 && x1 != 1)
      ans = (ans + solve(31, 1, 1, 1, x1 - 1, y1 - 1, kk).second) % 1000000007;
    cout << ans << '\n';
  }
}
