#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
const int B = 61;
// const int B = 3;
const int mod = 1e9 + 7;
int T;
ll n, m, S;
int f[B + 5][2][3][3], g[B + 5][2][3];
void Upd(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
int Solve(ll x, ll xs) {
  for (int i = 0; i <= B; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 3; ++k)
        for (int l = 0; l < 3; ++l) f[i][j][k][l] = 0;
  f[0][0][1][1] = 1;
  int nb, w;
  for (int i = 0; i < B; ++i) {
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 3; ++k)
        for (int l = 0; l < 3; ++l)
          if (f[i][j][k][l]) {
            // log("F %d %d %d %d=%d\n", i, j, k, l, f[i][j][k][l]);
            for (int v = 0; v < 2; ++v)
              for (int a = 0, b = (((xs >> i) & 1) ^ v); a < 2; ++a, b ^= 1) {
                nb = (a ^ b ^ j);
                w = (a + b + j > 1);
                Upd(f[i + 1][w][v == nb ? k : (v ? 0 : 2)][v == ((x >> i) & 1) ? l : (v ? 2 : 0)], f[i][j][k][l]);
              }
          }
  }
  // log("F=%d+%d\n", f[B][0][0][1], f[B][0][0][0]);
  return (f[B][0][0][1] + f[B][0][0][0]) % mod;
}
int Calc(ll x, ll xs) {
  if (!x) return 0;
  xs ^= x;
  // log("Calc %lld %lld\n", x, xs);
  int nb, w;
  for (int i = 0; i <= B; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 3; ++k) g[i][j][k] = 0;
  g[0][0][1] = 1;
  for (int i = 0; i < B; ++i) {
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 3; ++k)
        if (g[i][j][k]) {
          // log("G %d %d %d=%d\n", i, j, k, g[i][j][k]);
          for (int a = 0, b = ((xs >> i) & 1); a < 2; ++a, b ^= 1) {
            nb = (a ^ b ^ j);
            w = (a + b + j > 1);
            Upd(g[i + 1][w][((x >> i) & 1) == nb ? k : (nb ? 2 : 0)], g[i][j][k]);
          }
        }
  }
  // log("G=%d\n", g[B][0][0]);
  return g[B][0][0];
}
int main() {
#ifdef memset0
  freopen("K.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> T;
  while (T--) {
    cin >> n >> m;
    if (!n && !m) {
      cout << "0\n";
      continue;
    }
    S = ((n + 1 >> 1) & 1);
    for (int i = 1; i < B; ++i) {
      if (((n >> i) & 1) && !(n & 1)) S |= (1ll << i);
    }
    S ^= m;
    log("S=%lld\n", S);
    cout << (Solve(n, S) + Calc(m, S)) % mod << "\n";
  }
}