Problem: In modern cryptography much is tied to the algorithmic complexity of solving several problems. One of such problems is a discrete logarithm problem. It is formulated as follows: 

Let's fix a [finite field](https://en.wikipedia.org/wiki/Finite_field) and two it's elements a and b. One need to fun such x that a^x = b or detect there is no such x. 

It is most likely that modern mankind cannot solve the problem of discrete logarithm for a sufficiently large field size. For example, for a field of residues modulo prime number, primes of 1024 or 2048 bits are considered to be safe. However, calculations with such large numbers can place a significant load on servers that perform cryptographic operations. For this reason, instead of a simple module residue field, more complex fields are often used. For such field no fast algorithms that use a field structure are known, smaller fields can be used and operations can be properly optimized. 

Developer Nikolai does not trust the generally accepted methods, so he wants to invent his own. Recently, he read about a very strange field — [nimbers](https://en.wikipedia.org/wiki/Nimber), and thinks it's a great fit for the purpose. 

The field of nimbers is defined on a set of integers from 0 to 2^{2^k} - 1 for some positive integer k . Bitwise exclusive or (⊕) operation is used as addition. One of ways to define multiplication operation (⊙) is following properties: 

  * 0 ⊙ a = a ⊙ 0 = 0 
  * 1 ⊙ a = a ⊙ 1 = a 
  * a ⊙ b = b ⊙ a 
  * a ⊙ (b ⊙ c)= (a ⊙ b) ⊙ c 
  * a ⊙ (b ⊕ c) = (a ⊙ b) ⊕ (a ⊙ c) 
  * If a = 2^{2^n} for some integer n > 0, and b < a, then a ⊙ b = a ⋅ b. 
  * If a = 2^{2^n} for some integer n > 0, then a ⊙ a = 3/2⋅ a. 



For example: 

  *  4 ⊙ 4 = 6 
  *  8 ⊙ 8 = 4 ⊙ 2 ⊙ 4 ⊙ 2 = 4 ⊙ 4 ⊙ 2 ⊙ 2 = 6 ⊙ 3 = (4 ⊕ 2) ⊙ 3 = (4 ⊙ 3) ⊕ (2 ⊙ (2 ⊕ 1)) = (4 ⊙ 3) ⊕ (2 ⊙ 2) ⊕ (2 ⊙ 1) = 12 ⊕ 3 ⊕ 2 = 13. 
  * 32 ⊙ 64 = (16 ⊙ 2) ⊙ (16 ⊙ 4) = (16 ⊙ 16) ⊙ (2 ⊙ 4) = 24 ⊙ 8 = (16 ⊕ 8) ⊙ 8 = (16 ⊙ 8) ⊕ (8 ⊙ 8) = 128 ⊕ 13 = 141 
  * 5 ⊙ 6 = (4 ⊕ 1) ⊙ (4 ⊕ 2) = (4⊙ 4) ⊕ (4 ⊙ 2) ⊕ (4 ⊙ 1) ⊕ (1 ⊙ 2) = 6 ⊕ 8 ⊕ 4 ⊕ 2 = 8 



Formally, this algorithm can be described by following pseudo-code. 
    
    
    multiply(a, b) {  
       ans = 0  
       for p1 in bits(a)       // numbers of bits of a equal to one  
           for p2 in bits(b)   // numbers of bits of b equal to one  
              ans = ans xor multiply_powers_of_2(1 << p1, 1 << p2)  
       return ans;  
    }  
    multiply_powers_of_2(a, b) {  
        if (a == 1 or b == 1) return a * b  
        n = maximal value, such 2^{2^{n}} <= max(a, b)  
        power = 2^{2^{n}};  
        if (a >= power and b >= power) {  
            return multiply(power * 3 / 2, multiply_powers_of_2(a / power, b / power))  
        } else if (a >= power) {  
            return multiply_powers_of_2(a / power, b) * power  
        } else {  
            return multiply_powers_of_2(a, b / power) * power  
        }  
    }  
    

It can be shown, that this operations really forms a field. Moreover, than can make sense as game theory operations, but that's not related to problem much. With the help of appropriate caching and grouping of operations, it is possible to calculate the product quickly enough, which is important to improve speed of the cryptoalgorithm. More formal definitions as well as additional properties can be clarified in the wikipedia article at [link](https://en.wikipedia.org/wiki/Nimber). The authors of the task hope that the properties listed in the statement should be enough for the solution. 

Powering for such muliplication is defined in same way, formally a^{⊙ k} = \underbrace{a ⊙ a ⊙ ⋅⋅⋅ ⊙ a}_{k~times}.

You need to analyze the proposed scheme strength. For pairs of numbers a and b you need to find such x, that a^{⊙ x} = b, or determine that it doesn't exist. 

Input

In the first line of input there is single integer t (1 ≤ t ≤ 100) — number of pairs, for which you need to find the discrete logarithm.

In each of next t line there is a pair of integers a b (1 ≤ a, b < 2^{64}). 

Output

For each pair you should print one integer x (0 ≤ x < 2^{64}), such that a^{⊙ x} = b, or -1 if no such x exists. It can be shown, that if any such x exists, there is one inside given bounds. If there are several good values, you can output any of them. 

Example

Input


7
2 2
1 1
2 3
8 10
8 2
321321321321 2
123214213213 4356903202345442785


Output


1
1
2
4
-1
6148914691236517205
68943624821423112

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
using ModType = int;
struct VarMod {
  static ModType value;
};
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
const unsigned long long one = 1;
unsigned long long multiply(unsigned long long a, unsigned long long b);
unsigned long long multiply_powers_of_2(unsigned long long a,
                                        unsigned long long b) {
  if (a == 1 || b == 1) return a * b;
  unsigned long long n = 5;
  while ((one << (one << n)) > max(a, b)) {
    --n;
  }
  unsigned long long power = (one << (one << n));
  if (a >= power && b >= power) {
    return multiply(power * 3 / 2, multiply_powers_of_2(a / power, b / power));
  } else if (a >= power) {
    return multiply_powers_of_2(a / power, b) * power;
  } else {
    return multiply_powers_of_2(a, b / power) * power;
  }
}
unsigned long long multiply(unsigned long long a, unsigned long long b) {
  unsigned long long ans = 0;
  for (int i = 0; i < 64; i++) {
    if (a & (one << i)) {
      for (int j = 0; j < 64; j++) {
        if (b & (one << j)) {
          ans ^= multiply_powers_of_2(one << i, one << j);
        }
      }
    }
  }
  return ans;
}
unsigned long long memo[64][64];
unsigned long long multiply_powers_of_2_fast(unsigned long long a,
                                             unsigned long long b) {
  return memo[__builtin_ctzll(a)][__builtin_ctzll(b)];
}
unsigned long long multiply_fast(unsigned long long a, unsigned long long b) {
  unsigned long long ans = 0;
  for (int i = 0; i < 64; i++) {
    if (a & (one << i)) {
      for (int j = 0; j < 64; j++) {
        if (b & (one << j)) {
          ans ^= multiply_powers_of_2_fast(one << i, one << j);
        }
      }
    }
  }
  return ans;
}
template <typename T>
void crt(const vector<int>& p, const vector<int>& a, T& res) {
  assert(p.size() == a.size());
  auto inverse = [&](int q, int m) {
    q %= m;
    if (q < 0) q += m;
    int b = m, u = 0, v = 1;
    while (q) {
      int t = b / q;
      b -= t * q;
      swap(q, b);
      u -= t * v;
      swap(u, v);
    }
    assert(b == 1);
    if (u < 0) u += m;
    return u;
  };
  vector<int> x(p.size());
  for (int i = 0; i < (int)p.size(); i++) {
    assert(0 <= a[i] && a[i] < p[i]);
    x[i] = a[i];
    for (int j = 0; j < i; j++) {
      x[i] = (int)((long long)(x[i] - x[j]) * inverse(p[j], p[i]) % p[i]);
      if (x[i] < 0) x[i] += p[i];
    }
  }
  res = 0;
  for (int i = (int)p.size() - 1; i >= 0; i--) {
    res = res * p[i] + x[i];
  }
}
const unsigned long long M = ((one << 63) - 1) * 2 + 1;
vector<int> factors = {641, 6700417, 65537, 257, 17, 5, 3};
unsigned long long my_power(unsigned long long x, unsigned long long y) {
  unsigned long long res = 1;
  while (y > 0) {
    if (y & 1) {
      res = multiply_fast(res, x);
    }
    x = multiply_fast(x, x);
    y >>= 1;
  }
  return res;
}
map<unsigned long long, int> mp[7];
const int JUMP = 50000;
vector<unsigned long long> steps;
vector<unsigned long long> big_steps;
vector<int> Log(unsigned long long x) {
  vector<int> ret(factors.size());
  for (int iter = 0; iter < (int)factors.size(); iter++) {
    int f = factors[iter];
    assert(M % f == 0);
    unsigned long long y = my_power(x, M / f);
    unsigned long long big_step = big_steps[iter];
    ret[iter] = 0;
    while (true) {
      if (mp[iter].find(y) != mp[iter].end()) {
        ret[iter] = (ret[iter] + mp[iter][y]) % f;
        break;
      }
      y = multiply_fast(y, big_step);
      ret[iter] = ((ret[iter] + f - JUMP) % f + f) % f;
    }
  }
  return ret;
}
int main() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++) {
      memo[i][j] = multiply_powers_of_2(one << i, one << j);
    }
  }
  42;
  for (int iter = 0; iter < (int)factors.size(); iter++) {
    int f = factors[iter];
    unsigned long long step = my_power(M, M / f);
    steps.push_back(step);
    big_steps.push_back(my_power(step, JUMP));
    unsigned long long me = 1;
    for (int i = 0; i < JUMP; i++) {
      if (mp[iter].find(me) != mp[iter].end()) break;
      mp[iter][me] = i;
      me = multiply_fast(me, step);
    }
  }
  42;
  int tt;
  cin >> tt;
  while (tt--) {
    unsigned long long x, y;
    cin >> x >> y;
    auto xl = Log(x);
    auto yl = Log(y);
    bool ok = true;
    for (int i = 0; i < (int)factors.size(); i++) {
      if (xl[i] == 0) {
        if (yl[i] != 0) {
          ok = false;
          break;
        }
      } else {
        md = factors[i];
        yl[i] = (Mint(yl[i]) / Mint(xl[i]))();
      }
    }
    if (!ok) {
      cout << -1 << '\n';
    } else {
      unsigned long long res;
      crt(factors, yl, res);
      cout << res << '\n';
    }
    if (tt % 10 == 0) 42;
  }
  return 0;
}