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 <cstring>
#include <algorithm>
#include <cstdio>
#include <map>

using namespace std;
typedef long long ll;
typedef map<int,int>::iterator miter;
typedef map<int,int>::const_iterator cmiter;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
int _w;

int T, a, m;
map<int,int> fac[1000];

ll fmul( ll a, ll b, ll p ) {
	ll c = 0;
	while(b) {
		if( b & 1 ) c = (c + a) % p;
		a = (a << 1) % p;
		b >>= 1;
	}
	return c;
}
ll fpow( ll a, ll b, ll p ) {
	ll c = 1;
	while(b) {
		if( b & 1 ) c = fmul(c, a, p);
		a = fmul(a, a, p);
		b >>= 1;
	}
	return c;
}
void addfac( int x, map<int,int> &mp ) {
	for( int i = 2; i*i <= x; ++i )
		while( x % i == 0 )
			++mp[i], x /= i;
	if( x > 1 ) ++mp[x];
}
ll phi( const map<int,int> &mp ) {
	ll x = 1;
	for( cmiter it = mp.begin(); it != mp.end(); ++it )
		x *= (it->first - 1) * fpow(it->first, it->second-1, INFLL);
	return x;
}
ll calc( const map<int,int> &mp ) {
	ll x = 1;
	for( cmiter it = mp.begin(); it != mp.end(); ++it )
		x *= fpow(it->first, it->second, INFLL);
	return x;
}
void phi2( const map<int,int> &mp1, map<int,int> &mp2 ) {
	for( cmiter it = mp1.begin(); it != mp1.end(); ++it ) {
		addfac(it->first-1, mp2);
		if( it->second > 1 )
			mp2[it->first] += it->second-1;
	}
}

ll solve( int idx ) {
	if( fac[idx].empty() ) return 1;
	fac[idx+1].clear();
	ll p = calc( fac[idx] );
	phi2( fac[idx], fac[idx+1] );
	return fpow(a, solve(idx+1), p) + p;
}

int main() {
	_w = scanf( "%d", &T );
	while( T-- ) {
		_w = scanf( "%d%d", &a, &m );
		fac[0].clear();
		addfac( m, fac[0] );
		// printf( "m = %lld\n", calc( fac[0] ) );
		// printf( "phi(m) = %lld\n", phi( fac[0] ) );
		addfac( (int)phi( fac[0] ), fac[0] );
		// printf( "m * phi(m) = %lld\n", calc( fac[0] ) );
		printf( "%lld\n", solve(0) );
	}
	return 0;
}