#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define MAX 10100
#define INF 0x3f3f3f
#define LL unsigned long long
using namespace std;
LL gcd(LL a,LL b)
{
	LL c;
	while(b)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}
int main()
{
	LL n,m,j,i,t,k;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		if(n>m||n==0||m%n)
		{
			printf("-1\n");
			continue;
		}
		if(n==m)
		{
			printf("0\n");
			continue;
		}
		int flag=1;
		k=0;
		while(n!=m)
		{
			k++;
		    if(gcd(m/n,n)==1)
		    {
		    	flag=0;
		    	break;
		    }
			n*=gcd(m/n,n);
		}
		if(flag)
		printf("%lld\n",k);
		else
		printf("-1\n");
	}
	return 0;
}