p为质数则可以用快速幂求幂元，若p不是质数则不能用这个方法
同余：a，b两个数若同余，则它们对m取模的值是一样的
求逆元：有一个数b，求一个数x，使得bx同余于1(p)(即b乘x%p后余1)
本题p为质数，费马定理：若b和p互质则b^p-1%p同余于1
b^p-1==bb^p-2,所以b^p-2为b的逆元，所以可以用快速幂求b^p-2(即b的逆元)，若b与p不互质(即b为p的倍数)，则无解

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int qmi(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;
    scanf("%d",&n);
    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);
        LL res=qmi(a,p-2,p);
        if(a%p)//如果a与p互质
        {
            printf("%d\n",res);

        }
        else
        puts("impossible");
    }
    return 0;
}