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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

int calcphi(int n) {
	int ret = 1;
	for (int i = 2; i*i <= n; ++i) if (n%i == 0) {
		ret *= i - 1; n /= i;
		while (n%i == 0) n /= i, ret *= i;
	}
	if (n != 1) ret *= n - 1;
	return ret;
}
int pw(int x, ll n, int mod) { int ret = 1; while (true) { if (n & 1) ret = (ll)ret*x%mod; if ((n >>= 1) == 0) return ret; x = (ll)x*x%mod; } }

// a*x+b*y=ret
int egcd(int a, int b, int &x, int &y) {
	if (b == 0) { x = 1; y = 0; return a; }
	int g = egcd(b, a%b, y, x); // b*y+(a%b)*x=g -> a*x+b*y-(a/b)*b*x=g 
	y -= (a / b)*x;
	//printf("\t\t%d*%d+%d*%d=%d\n", a, x, b, y, g);
	return g;
}

int modsolve(int a, int b, int n) { // a*x=b (mod n)
	int x, y; int g = egcd(a, n, x, y); // a*x=g (mod n)
	assert(b%g == 0);
	int ret = (ll)x*(b / g) % n; if (ret < 0) ret += n; return ret;
}

// a^ret-ret | n, ret>=n
ll solve(int a, int n) {
	if (n == 1) return 1;
	// a^(x+y*phi(n))=a^x -> x+y*phi(n)=a^x (mod n) -> y*phi(n)=a^x-x (mod n) -> a^x-x | gcd(phi(n),n)
	int phi = calcphi(n), gg = gcd(n, phi);
	ll x = solve(a, gg);
	ll lhs = (pw(a, x, n) - x%n + n) % n;
	if (lhs%gg != 0) fprintf(stderr,"\terrsolve(%d,%d) [phi=%d, gg=%d lhs=%lld x=%lld]\n", a, n, phi, gg, lhs, x);
	assert(lhs%gg == 0);
	int y = modsolve(phi / gg, lhs / gg, n / gg);
	ll ret = x + (ll)y*phi;
	if (ret < n) ret += (ll)n*(phi / gg);
	//int chklhs = pw(a, ret, n), chkrhs = ret%n;	printf("\tsolve(%d,%d)=%lld [phi=%d, gg=%d lhs=%lld x=%lld y=%d] -> {%d,%d}\n", a, n, ret, phi, gg, lhs, x, y, chklhs, chkrhs);
	return ret;
}

void run() {
	int a, n;
	scanf("%d%d", &a, &n);
	ll ret = solve(a, n);
	printf("%lld\n", ret);
}

int main() {
	int n; scanf("%d", &n); FORE(i, 1, n) run();
	return 0;
}