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

long long a,p;
int main()
{
	freopen("drei.in","r",stdin);
	freopen("drei.out","w",stdout);
	int t,e;
	cin>>t;
	int m=-1;
	for(int i=1;i<=t;i++)
	{
		cin>>a>>p;
		e=a;
		if(a%p==1)
		{
			cout<<1<<endl;
			break;
		}	
		else
		{
			for(int j=1;j<=100000;j++)
			{
				a=a*e;
				if(a%p==1)
				{
					m=j+1;
					cout<<m<<endl;
					break;
				}	
			}
			if(m==-1)
				cout<<m<<endl;
		}
		m=-1;
	}
	return 0;
}