#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int t,a,p;
int main()
{
	freopen("drei.in","r",stdin);
	freopen("drei.out","w",stdout);
	
	cin>>t;
	for (int i=1; i<=t; i++)
	{
		scanf("%d%d",&a,&p);
		int k=a%p;
		int s=k;
		for (int j=2; j<=1000000000; j++)
		{
			if (a%p==0 || p%a==0)
			{
				cout<<"-1"<<endl;
				break;
			}
			else
			{
				s=(s*k)%p;
				if (s==1)
				{
					cout<<j<<endl;
					break;
				}
			}		
		}
	}
	return 0;
}