#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int qsm(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(ll)res*a%p;
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

int main(){
    int n;
    cin>>n;

    while(n--){
        int a,p;
        cin>>a>>p;

        if(a%p) cout<<qsm(a,p-2,p)<<endl;  //如果a是p的倍数，a%p一定等于0，不可能有逆元
        else cout<<"impossible"<<endl;
    }
}