#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

// a^p-2%p
int qmi(int a, int b, int p){
    LL res=1;
    while(b){
        if(b&0x01) res=res*a%p;
        b>>=1;
        a=(LL)a*a%p;
    }
    return res;
}


int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        int a, p;
        scanf("%d%d", &a, &p);
        int res=qmi(a, p-2, p);
        if(a%p) cout<<res<<endl;
        else cout<<"impossible"<<endl;
    }

    return 0;
}