Problem: Process the Q queries below.

* You are given two integers A_i and M_i. Determine whether there exists a positive integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i), and find one if it exists.

Constraints

* 1 \leq Q \leq 100
* 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
* 1 \leq M_i \leq 10^9(1 \leq i \leq Q)



Examples

Input

4
2 4
3 8
9 6
10 7


Output

4
11
9
2


Input

3
177 168
2028 88772
123456789 987654321


Output

7953
234831584
471523108231963269

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef __int128 lll;

lll phi(lll n) {
  lll result = n;
  for(int i = 2; i * i <= n; ++i) {
    if(n % i == 0) {
      while(n % i == 0)n /= i;
      result -= result / i;
    }
  }
  if(n > 1) result -= result / n;
  return result;
}

lll powMod(lll a, lll b, lll n) {
  if (b == 0) return 1;
  lll res = 1;
  while (b > 1) {
    if (b & 1) res = (a * res) % n;
    a = (a * a) % n;
    b /= 2;
  }
  return (a * res) % n;
}

lll extendedEuclid(lll a, lll b, lll &x, lll &y) {
  if (a == 0) { x = 0; y = 1; return b; }
  lll x1, y1, d = extendedEuclid(b % a, a, x1, y1);
  x = y1 - (b / a) * x1; y = x1;
  return d;
}

lll multInv(lll n, lll p) {
  lll x, y;
  extendedEuclid(n, p, x, y);
  x = ((x % p) + p) % p;
  return x % p;
}

ll solve(lll a, lll m) {
  if (m <= 1) {
    return 1e9;
    // lll power = 1;
    // for (lll k = 1; k <= m; k++) {
    //   power = power * a % m;
    //   if (power == (k % m)) {
    //     return (ll)k;
    //   }
    // }
    // return -1;
  } else {
    lll phim = phi(m);
    lll y, z;
    lll g = extendedEuclid(m, phim, y, z);
    lll solution = solve(a, g);
    lll power = powMod(a, solution, m);

    // lll mod = phim * (m / g);
    // lll minus = y * m % mod * ((power - solution) / g) % mod;
    // lll res = ((power - minus) % mod + mod) % mod;
    // return (ll)res;

    lll res = (((power - solution) % m / g % m) + m) % m;
    res *= multInv(phim / g, m / g);
    res = (res % m + m) % m;
    return solution + (ll)res * phim;
  }
}

int main() {
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    ll a, m;
    scanf("%lld %lld", &a, &m);
    printf("%lld\n", solve(a, m));
  }
  return 0;
}