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>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 40005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}

int64 A,M;
int64 phi(int64 x) {
	int64 t = x;
	for(int i = 2 ; i <= x / i ; ++i) {
		if(x % i == 0) {
			t = t / i * (i - 1);
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) t = t / x * (x - 1);
	return t;
}
int64 gcd(int64 a,int64 b) {
	return b == 0 ? a : gcd(b,a % b);
}
int64 fpow(int64 x,int64 c,int64 M) {
	int64 res = 1,t = x;
	while(c) {
		if(c & 1) res = res * t % M;
		t = t * t % M;
		c >>= 1;
	}
	return res;
}
void exgcd(int64 a,int64 b,int64 &x,int64 &y) {
	if(b == 0) {x = 1;y = 0;}
	else {
		exgcd(b,a % b,y,x);
		y -= a / b * x;
	}
}
int64 mul(int64 a,int64 b,int64 M) {
	int64 res = 0,t = a;
	while(b) {
		if(b & 1) res = (res + t) % M;
		t = (t + t) % M;
		b >>= 1;
	}
	return res;
}
int64 Calc(int64 a,int64 m) {
	if(m == 1) return 100;
	int64 eu = phi(m),g = gcd(eu,m);
	int64 y = Calc(a,g);
	int64 a1 = fpow(a,y,m),a2 = y % eu;
	int64 x,t;
	exgcd(m,eu,x,t);
	int64 mod = m * eu / g;
	x = (x % (eu / g) + eu / g) % (eu / g);
	x = x * (a2 - a1) / g;
	x = (x % mod + mod) % mod;
	x = (mul(x,m,mod) + a1) % mod;
	while(x < 100) x += mod;
	return x;
}
void Solve() {
	read(A);read(M);
	int64 x = Calc(A,M);
	out(x);enter;
	//if(fpow(A,x,M) == x % M) {puts("YES");}
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	int Q;
	read(Q);
	while(Q--) Solve();
}