#include <iostream>
#include <cstdio>
#include <cmath>
int a,b;
int x;
int c,n; 
using namespace std;
int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	freopen("drei.in","r",stdin);
	freopen("drei.out","w",stdout);
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int y=0;
		c=1;
		cin>>a>>b;
		x=a;
		for(int j=1;j<=200;j++)
		{
			if(x%b==1)
			{
				cout<<c<<endl;
				y=10;
				break;
			}
			x*=a;
			c++;
		}
		if(y==0) cout<<-1<<endl;
	}
	return 0;
}