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<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
int phi(int x)
{
	int r = 1;
	for (int i = 2;; i++)
	{
		if (i*i > x)break;
		if (x%i == 0)
		{
			int t = i - 1;
			x /= i;
			for (;;)
			{
				if (x%i == 0)x /= i, t *= i;
				else break;
			}
			r *= t;
		}
	}
	if (x != 1)r *= x - 1;
	return r;
}
typedef long long ll;
ll po(ll a, ll b, ll m)
{
	if (b == 0)return 1;
	ll z = po(a, b / 2, m);
	z = z*z%m;
	if (b & 1)z = z*a%m;
	return z;
}
typedef pair<ll, ll>pii;
pii calc(ll a, ll m)
{
	if (m == 1)return make_pair(0, 0);
	ll pm = phi(m);
	pii z = calc(a, pm);
	return make_pair(po(a, z.first + pm * 50, m), z.first);
}
pii extgcd(ll a, ll b)//ax+by=gcd(a,b) の解(x,y)を返す
{
	if (a == 0)
	{
		if (b > 0)return make_pair(0, 1);
		else return make_pair(0, -1);
	}
	else if (b == 0)
	{
		if (a > 0)return make_pair(1, 0);
		else return make_pair(-1, 0);
	}
	else if (abs(a) < abs(b))
	{
		ll p = b / a, q = b - p*a;
		pii z = extgcd(a, q);
		return make_pair(z.first - p*z.second, z.second);
	}
	else
	{
		ll p = a / b, q = a - p*b;
		pii z = extgcd(q, b);
		return make_pair(z.first, z.second - p*z.first);
	}
}
ll gcd(ll a, ll b)
{
	if (a == 0)return b;
	if (b == 0)return a;
	for (;;)
	{
		if (a < b)swap(a, b);
		a %= b;
		if (a == 0)return b;
	}
}
int main()
{
	int data;
	scanf("%d", &data);
	for (int p = 0; p < data; p++)
	{
		ll a, m;
		scanf("%lld%lld", &a, &m);
		ll pm = phi(m);
		pii r = calc(a, m);
		//printf("%lld %lld   %lld\n", r.first, r.second, gcd(m, phi(m)));
		ll g = gcd(m, pm);
		pii z = extgcd(m, pm);
		//printf("%lld %lld\n", z.first, z.second);
		ll ans = (r.second - r.first) / g*z.first%pm*m + r.first;
		ans %= (m*pm);
		ans += m*pm;
		ans %= (m*pm);
		if (ans < 35)ans += (35 + m*pm) / (m*pm)*(m*pm);
		printf("%lld\n", ans);
		//printf("%lld %lld\n", po(a, ans, m), ans%m);
	}
}