#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int KSM(int a,int b,int p)
{
int ans=1;
for(;b;)
{
if(b&1)ans=ll(ans)*a%p;
b>>=1,a=ll(a)*a%p;
}return ans;
}
int n,a,p;
int main()
{
scanf("%d",&n);
for(;n--;)
{
scanf("%d%d",&a,&p);
if(a%p==0)printf("impossible\n");
else printf("%d\n",KSM(a,p-2,p));
}
return 0;
}