#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
inline long long mod(long long a, long long m) {
return (a % m + m) % m;
}
long long pow(long long a, long long n, long long m) {
if (n == 0) return 1 % m;
long long t = pow(a, n / 2, m);
t = mod(t * t, m);
if (n & 1) t = mod(t * a, m);
return t;
}
vector<pair<long long, long long> > prime_factor(long long n) {
vector<pair<long long, long long> > res;
for (long long i = 2; i*i <= n; ++i) {
if (n % i == 0) {
int exp = 0;
while (n % i == 0) {
++exp;
n /= i;
}
res.push_back(make_pair(i, exp));
}
}
if (n != 1) res.push_back(make_pair(n, 1));
return res;
}
long long GCD(long long a, long long b) {
if (b == 0) return a;
else return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
long long g = GCD(a, b);
return a / g * b;
}
vector<pair<long long, long long> > divA;
long long inv(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t*b; swap(a, b);
u -= t*v; swap(u, v);
}
return mod(u, m);
}
long long gcd(long long a, long long b) {
if (b == 0) return a;
else return gcd(b, a % b);
}
pair<long long, long long> ChineseRem(long long b1, long long m1, long long b2, long long m2) {
long long x = 0, m = 1;
long long a = m, b = b1 - x, d = gcd(m1, a);
if (b % d != 0) return make_pair(0, -1);
long long t = mod(b / d * inv(a / d, m1 / d), m1 / d);
x += m * t;
m *= m1 / d;
a = m, b = b2 - x, d = gcd(m2, a);
if (b % d != 0) return make_pair(0, -1);
t = mod(b / d * inv(a / d, m2 / d), m2 / d);
x += m * t;
m *= m2 / d;
return make_pair(x % m, m);
}
long long solve(long long A, long long M) {
if (A == 0) return M;
if (A == 1) return 1;
if (M == 1) return 50;
long long nM = M;
for (int i = 0; i < divA.size(); ++i) {
long long p = divA[i].first;
while (nM % p == 0) nM /= p;
}
vector<pair<long long, long long> > divM = prime_factor(nM);
for (int i = 0; i < divM.size(); ++i) {
long long p = divM[i].first;
nM *= p - 1;
nM /= p;
}
long long y = solve(A, nM);
long long rM = pow(A, y, M);
long long rnM = pow(A, y, nM);
pair<long long, long long> pres = ChineseRem(rM, M, rnM, nM);
long long lcm = pres.second;
long long res = pres.first;
while (res < 50) res += lcm;
/*
COUT(M);
COUT(divM);
COUT(nM);
COUT(lcm);
COUT(res);
COUT(mod(res, M));
COUT(pow(A, res, M));
*/
return res;
}
int main() {
int Q;
while (cin >> Q) {
for (int i = 0; i < Q; ++i) {
long long a, m; cin >> a >> m;
divA = prime_factor(a);
long long res = solve(a, m);
cout << res << endl;
/*
COUT(divA);
COUT(mod(res, m));
COUT(pow(a, res, m));
*/
}
}
}