#include<iostream>
using namespace std;
const int N=100010;
int n;
int a,b,p;
long long res;
void power(int a,int b,int p){
res=1%p;
while(b){
if(b&1){
res=(long long)res*a %p;
}
b>>=1;
a=(long long)a*a %p;
}
}
int main(){
cin>>n;
while(n--){
cin>>a>>p;
power(a,p-2,p);
if(a%p==0){
cout<<"impossible"<<endl;
}else{
cout<<res<<endl;
}
res=0;
}
return 0;
}