#include <iostream>

using namespace std;
int qmi(int a,int p){
    int res=1%p;
    int b=p-2;
    while(b){
        if(b&1) res=(long long)res*a%p;
        b=b>>1;
        a=(long long)a*a%p;
    }
    return res;
}
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    cin>>n;
    while(n--){
        int a,p;
        cin>>a>>p;
        int res=qmi(a,p);
        if(gcd(a,p)==1)
        cout<<res<<endl;
        else
            cout<<"impossible"<<endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}