#include <iostream>#include <algorithm>#include <cmath>typedef long long LL;using namespace std;bool isPrime[60000];int prime[6100], primeCnt;int a, z;int p[50], c[50], pcnt;LL factor[30000];int fcnt;inline void init(){ for(int i = 2; i < 60000; ++i) isPrime[i] = 1; for(int i = 2; i < 250; ++i) if(isPrime[i]) for(int j = i; i*j < 60000; ++j) isPrime[i*j] = 0; primeCnt = 0; for(int i = 2; i < 60000; ++i) if(isPrime[i]) prime[primeCnt++] = i;}inline LL euler(int x){ LL y = 1; for(int i = 0; x >= prime[i] && i < primeCnt; ++i) { if(x % prime[i] == 0) { y *= prime[i] - 1; x /= prime[i]; while(x % prime[i] == 0) { x /= prime[i]; y *= prime[i]; } } } if(x != 1) y *= x - 1; return y;}void DFS(int x, int s){ if(x == pcnt) { factor[fcnt++] = s; return; } DFS(x+1, s); for(int i = 1; i <= c[x]; ++i) { s *= p[x]; DFS(x+1, s); }}LL check(LL x){ if(x == 1LL) return (LL)(a % z); LL rmd = check(x/2)*check(x/2) % z; if(x % 2 == 1) rmd = rmd * a % z; return rmd;}int main(void){ init(); int T; cin >> T; while(T --) { cin >> a >> z; if(a == 1 || z == 1) { cout << "9n"; continue; } LL eu = euler(z); pcnt = 0; for(int i = 0; i < primeCnt; ++i) { if(eu % prime[i] == 0) { p[pcnt] = prime[i]; c[pcnt] = 0; while(eu % prime[i] == 0) { eu /= prime[i]; ++ c[pcnt]; } ++pcnt; } } if(eu != 1LL) { p[pcnt] = eu; c[pcnt] = 1; ++ pcnt; } fcnt = 0; DFS(0, 1); sort(factor, factor+fcnt); bool flag = 0; for(int i = 0; i < fcnt-1; ++i) { if(check(factor[i]) == 1LL) { cout << factor[i]*6 + 3 << endl; flag = 1; break; } } if(flag == 0) cout << factor[fcnt-1]*6 + 3 << endl; }}
