#include<stdio.h>
int main()
{
	freopen("drei.in","r",stdin);
	freopen("drei.out","w",stdout);
	int t;
	unsigned long long i,a,x,p,n,j;
	scanf("%d",&t);
	for(i=0;i<t;i++)
	{
	  scanf("%llu%llu",&a,&p);
	  if(p%a==0||p<=1)
	    {printf("%d\n",-1);continue;}
	  for(x=1;;x++)
	  {
	    n=1;
	    for(j=1;j<=x;j++)
	      n=n*a%p;
	    if(n==1)
	      {printf("%llu\n",x);break;}
	  }
    }
	return 0;
}