#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128_t int128;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

ll lcm(ll a, ll b){
    return a/__gcd(a, b)*b;
}

ll extgcd(ll x, ll y, ll &u, ll &v){
	ll d = x;
	if(y != 0){
		d = extgcd(y, x%y, v, u);
		v -= (x/y)*u;
	} else {
		u = 1;
		v = 0;
	}
	return d;
}

int128 extgcd128(int128 x, int128 y, int128 &u, int128 &v){
	int128 d = x;
	if(y != 0){
		d = extgcd128(y, x%y, v, u);
		v -= (x/y)*u;
	} else {
		u = 1;
		v = 0;
	}
	return d;
}

void chrm_coprime(ll &a, ll &m, ll b, ll n){
	ll u, v;
	extgcd(m, n, u, v);
	a = a*n*v+b*m*u;
	m = m*n;
	a %= m;
	if(a<0) a += m;
}

void chrm128(int128 &a, int128 &m, int128 b, int128 n){
	a = a%m+m; b = b%n+n;
	int128 a2 = a, m2 = m;
	int128 u, v;
	int128 g = extgcd128(m, n, u, v);
	//if(a%g!=b%g) cerr<<"WARNING: "<<a<<" != "<<b<<" mod gcd("<<m<<", "<<n<<")"<<endl;
	if(a%g!=b%g) cerr<<"NG"<<endl;
	//cerr<<m*u+n*v<<" "<<g<<endl;
	u *= (b-a)/g; v *= (b-a)/g;
	//cerr<<m*u+n*v<<" "<<b-a<<endl;
	//cerr<<"prev"<<a%m<<endl;
	a = m*u+a;
	//cerr<<"next"<<a%m<<endl;
	//cerr<<m<<" "<<u<<" "<<m*u/u-m<<endl;
	//cerr<<m<<" * "<<n/g<<" "<<m/g*n/n*g-m<<endl;
	m *= n/g;
	a %= m;
	if(a<0) a += m;
	//if(a%m2!=a2 || a%n!=b%n) cerr<<"NG2"<<endl;
	//cerr<<"verify4: "<<a%m2<<"="<<a2<<" and "<<a%n<<"="<<b%n<<endl;
	return;
	/*
	int128 c = a%g;
	m /= g; a /= g; n /= g; b /= g;
	a = a*n*v+b*m*u;
	a = a*g+c;
	m = m*n*g;
	a %= m;
	if(a<0) a += m;
	cerr<<"verify4: "<<a%m2<<"="<<a2%m<<" and "<<a%n<<"="<<b%n<<endl;
	*/
}

void chrm(ll &a, ll &m, ll b, ll n){
	int128 a2 = a, m2 = m, b2 = b, n2 = n;
	chrm128(a2, m2, b2, n2);
	a = a2; m = m2; b = b2; n = n2;
}
ll tot(ll m){
	ll res = 1;
	for(ll i = 2; i*i <= m; i++){
		if(!(m%i)){
			res *= i-1;
			m /= i;
			while(!m%i){
				m /= i;
				res *= i;
			}
		}
	}
	if(m>1) res *= m-1;
	return res;
}

ll pow_mod(ll a, ll r, ll m){
	ll x = 1;
	while(r){
		if(r&1) (x*=a)%=m;
		(a*=a)%=m;
		r>>=1;
	}
	return x;
}


ll a, m, m_org;

random_device rnd;

void solve(){
	//a = rnd()%1000000001;
	//m = rnd()%1000000000+1;
	//a %= 10;
	cin>>a>>m;
	a %= m;
	m_org = m;
	ll x = 0, n = 1, a2 = a;
	for(ll i = 2; a2>1; i++){
		if(i*i>2*a2) i = a2;
		if(a2%i) continue;
		while(a2%i==0) a2 /= i;
		if(m%i==0){
			ll j = 1;
			while(m%i==0){
				m /= i;
				j *= i;
			}
			chrm(x, n, 0, j);
		} else if(i==m) break;
	}
	//cerr<<"AA"<<m<<endl;
	for(ll i = 2; m>1; i++){
		//cerr<<i<<" "<<m<<endl;
		if(i*i>m) i = m;
		if(m%i) continue;
		ll j = 1;
		while(m%i==0){
			m /= i;
			j *= i;
		}
		//cerr<<i<<" "<<j<<endl;
		if(__gcd(a, i)>1);
		else {
			ll y = x+n, l = (i-1), j2 = 1, g = (x+n)%l;
			while(j>j2){
				//cerr<<y<<" % "<<l<<" "<<j2<<endl;
				//cerr<<pow_mod(a, y, j2)<<" = "<<y%j2<<" = "<<1<<endl;
				//if(a==3) cerr<<y<<" "<<l<<endl;
				ll b2 = pow_mod(a, y%l+l, j2*i)-1;
				ll c2 = y%(j2*i)-1;
				//cerr<<pow_mod(a, y%l+l, j2*i)<<" "<<y%(j2*i)<<endl;
				//cerr<<"b2 "<<b2<<" "<<b2%j2<<endl;
				ll b = 	(b2-c2)/j2;
				y -= (b)*l;
				l *= i; j2 *= i;
				y = y%l+l;
			}
			//cerr<<pow_mod(a, y, j2)<<" = "<<y%j2<<" = "<<1<<endl;
			//cerr<<"verify2: "<<y%j2<<" "<<pow_mod(a, y, j2)<<endl;
			//cerr<<"from: x="<<x<<" n="<<n<<" y="<<y<<" l="<<l<<endl;
			chrm(x, n, y, l);
			//cerr<<"to: x="<<x<<" n="<<n<<" y="<<y<<" l="<<l<<endl;
			//cerr<<"verify3: "<<x%(m_org/m)<<" "<<pow_mod(a, x, m_org/m)<<endl;
		}
	}
	x %= m_org*tot(m_org);
	while(x<100) x += m_org*tot(m_org);
	while(x%m_org!=pow_mod(a, x, m_org)) x++;
	cout<<x<<endl;
	cerr<<"verify: "<<x%m_org<<" "<<pow_mod(a, x, m_org)<<endl;
	if(x%m_org!=pow_mod(a, x, m_org) || x>2e18){
		//cout<<-1<<endl;
		cerr<<"CORNER: "<<a<<" "<<m_org<<endl;
		//while(1);
	}
}

int main(){
	int q;
	cin>>q;
	while(q--) solve();
	return 0;
}


Measured memory_bytes: 256