#include <bits/stdc++.h>
using namespace std;

namespace {

constexpr int mod = 1'000'000'007;

constexpr int add(int a, int b) {
  return a + b >= mod ? a + b - mod : a + b;
}
constexpr int sub(int a, int b) {
  return a - b < 0 ? a - b + mod : a - b;
}
constexpr int mul(int64_t a, int64_t b) {
  return static_cast<int>(a * b % mod);
}

int visc;
int vis1[64][2][2][2];
int dp1[64][2][2][2];

bool xd[64];
bool d1[64], d2[64];

int go1(int p, bool any1, bool any2, bool carry) {
  if (p == -1) {
    return not carry;
  }
  if (vis1[p][any1][any2][carry] == visc) {
    return dp1[p][any1][any2][carry];
  }
  vis1[p][any1][any2][carry] = visc;

  int ans = 0;
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      if (not any2 and (i ^ j ^ xd[p]) > d2[p])
        continue;
      for (int b : {0, 1}) {
        if (not any1 and (i + j + b) % 2 > d1[p])
          continue;
        if (i + j + b > 1) {
          if (not carry)
            continue;
          ans = add(ans, go1(p - 1, any1 or (i + j + b) % 2 < d1[p], any2 or (i ^ j ^ xd[p]) < d2[p], b));
        } else {
          if (carry)
            continue;
          ans = add(ans, go1(p - 1, any1 or (i + j + b) % 2 < d1[p], any2 or (i ^ j ^ xd[p]) < d2[p], b));
        }
      }
    }
  }

  cout << "dp1[" << p << "][" << any1 << "][" << any2 << "][" << carry << "] = " << ans << '\n';
  return dp1[p][any1][any2][carry] = ans;
}

int solve1(uint64_t x, uint64_t fi, uint64_t se) {
  memset(d1, 0, sizeof(d1));
  memset(d2, 0, sizeof(d2));

  int xdc = 63;
  for (uint64_t o = x; o; o /= 2)
    xd[xdc--] = o & 1;

  int d1c = 63;
  for (uint64_t o = fi; o; o /= 2)
    d1[d1c--] = o & 1;

  int d2c = 63;
  for (uint64_t o = se; o; o /= 2)
    d2[d2c--] = o & 1;

  visc += 1;
  return go1(63, 0, 0, 0);
}

int vis2[64][2][2][2];
int dp2[64][2][2][2];

int go2(int p, bool any1, bool any2, bool carry) {
  if (p == -1) {
    return not carry;
  }
  if (vis2[p][any1][any2][carry] == visc) {
    return dp2[p][any1][any2][carry];
  }
  vis2[p][any1][any2][carry] = visc;
  int ans = 0;
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      if (not any2 and (i ^ j ^ xd[p]) > (i + j + carry) % 2)
        continue;
      for (int b : {0, 1}) {
        if (not any1 and (i + j + b) % 2 > d1[p])
          continue;
        if (i + j + b > 1) {
          if (not carry)
            continue;
          ans = add(ans, go1(p - 1, any1 or (i + j + b) % 2 < d1[p], any2 or (i ^ j ^ xd[p]) < (i + j + carry) % 2, b));
        } else {
          if (carry)
            continue;
          ans = add(ans, go1(p - 1, any1 or (i + j + b) % 2 < d1[p], any2 or (i ^ j ^ xd[p]) < (i + j + carry) % 2, b));
        }
      }
    }
  }
  return dp2[p][any1][any2][carry] = ans;
}

int solve2(uint64_t x, uint64_t n) {
  memset(d1, 0, sizeof(d1));

  int xdc = 63;
  for (uint64_t o = x; o; o /= 2)
    xd[xdc--] = o & 1;

  int d1c = 63;
  for (uint64_t o = n; o; o /= 2)
    d1[d1c--] = o & 1;

  visc += 1;
  int ret = go2(63, 0, 0, 0);
  cout << "solve2(" << x << ", " << n << ") = " << ret << '\n';
  return ret;
}

int solve(uint64_t n, uint64_t m) {
  uint64_t x = m;
  for (uint64_t v = n / 4 * 4; v <= n; ++v)
    x ^= v;

  cout << "x = " << x << endl;

  int ans = 0;
  if (n > 0) {
    ans = add(ans, solve1(x, n - 1, n));
    ans = sub(ans, solve2(x, n - 1));
  }
  if (m > 0) {
    ans = add(ans, solve1(x, m - 1, m));
    ans = sub(ans, solve1(x, m - 1, m - 1));
  }
  return ans;
}

} // namespace

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    uint64_t n, m;
    cin >> n >> m;
    cout << solve(n, m) << '\n';
  }
  return 0;
}