#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
unsigned long long nim_mul(unsigned long long a, unsigned long long b,
                           int dep = 1 << 6) {
  static const int tabsz = 1 << 8;
  static unsigned long long table[tabsz][tabsz];
  if (a > b) swap(a, b);
  if (a <= 1) return (a) ? (b) : 0;
  if (b < tabsz && table[a][b]) return table[a][b];
  while (b < (1ull << (dep >> 1))) dep >>= 1;
  int half = dep >> 1;
  unsigned long long M = 1ull << half;
  unsigned long long aH = a >> half, aL = a & (M - 1);
  unsigned long long bH = b >> half, bL = b & (M - 1);
  unsigned long long t0 = nim_mul(aL, bL, half);
  unsigned long long t1 = nim_mul(aL ^ aH, bL ^ bH, half);
  unsigned long long t2 = nim_mul(aH, bH, half);
  unsigned long long ret = nim_mul(t2, M >> 1, half) ^ ((t1 ^ t0) << half) ^ t0;
  (b < tabsz) && (table[a][b] = ret, 0);
  return ret;
}
void exgcd(long long a, long long b, long long& x, long long& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}
long long inv(long long a, long long n) {
  long long x, y;
  exgcd(a, n, x, y);
  return (x < 0) ? (x + n) : x;
}
const unsigned long long F = ~0ull;
vector<unsigned long long> pF{3, 5, 17, 257, 641, 65537, 6700417};
unsigned long long add(unsigned long long a, unsigned long long b) {
  unsigned long long s = a + b;
  s = s + (s < a);
  return (s == F) ? (0) : (s);
}
unsigned long long mul(long long a, long long b) {
  long long rt = 0;
  for (; b; b >>= 1, a = add(a, a)) {
    if (b & 1) {
      rt = add(rt, a);
    }
  }
  return rt;
}
unsigned long long crt(vector<int> as) {
  unsigned long long ret = 0;
  int n = as.size();
  for (int i = 0; i < n; i++)
    ret = add(ret, mul(as[i] * (F / pF[i]), inv(F / pF[i] % pF[i], pF[i])));
  return ret;
}
unsigned long long nim_pow(unsigned long long a, unsigned long long p) {
  unsigned long long rt = 1;
  for (; p; p >>= 1, a = nim_mul(a, a)) {
    if (p & 1) {
      rt = nim_mul(rt, a);
    }
  }
  return rt;
}
int work(unsigned long long a, unsigned long long b, int p) {
  int C = sqrt(p + 0.5);
  map<unsigned long long, int> G;
  unsigned long long pb = b;
  for (int i = 1; i <= C; i++) {
    pb = nim_mul(pb, a);
    G[pb] = i;
  }
  unsigned long long pac = nim_pow(a, C), pa = 1;
  for (int L = 0; L < p;) {
    pa = nim_mul(pa, pac);
    L += C;
    if (G.count(pa)) {
      return L - G[pa];
    }
  }
  return -1;
}
int solve(unsigned long long a, unsigned long long b, int p) {
  return work(nim_pow(a, F / p), nim_pow(b, F / p), p);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T;
  unsigned long long a, b;
  cin >> T;
  while (T--) {
    cin >> a >> b;
    vector<int> ra;
    bool suc = true;
    for (auto p : pF) {
      int x = solve(a, b, p);
      if (x < 0) {
        suc = false;
        break;
      }
      ra.push_back(x);
    }
    if (suc) {
      unsigned long long t;
      cout << (t = crt(ra)) << '\n';
    } else {
      cout << "-1\n";
    }
  }
  return 0;
}
