#include <bits/stdc++.h> #define rep(i,n) for (int i=0; i < (n); i++) using namespace std; using ll = long long; int main(){ int testcase; cin>> testcase; while(testcase--){ ll A,P; cin>>A>>P; // Aが素数かどうか。 bool pflg = false; if(A==1){ cout << -1 << endl; pflg = true; } for(int i=2; i*i<A; i++){ if(A%i==0){ cout << -1 << endl; pflg = true; } } if(pflg) continue; // Aが素数の時 ll rA=A; for(ll i=P; i>0; i--){ for(ll j=0; j<P; j++){ A *= rA; A %= P; } } cout << A << endl; } }