Untitled

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <numeric>
#include <cstdio>
#include <list>
#include <cassert>
#include <climits>
#include <cassert>

using namespace std;

#define IN(type, name)\
	type name;\
	cin >> name;

#define For(var, constant, init) for (int var = init; var < constant; var++)

#define Sp << ' ' <<
#define End << '\n'

#define ll long long
#define ull unsigned long long
#define uint unsigned int

#define MOD 1000000007

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

bool isPerfect(ll n) {
	ll sq = sqrt(n);
	while(sq * sq > n) sq--;
	while(sq * sq < n) sq++;

	return sq * sq == n;
}

ll factorize(ll x) {
	ll cnt = 0;
	while (x % 2 == 0) {cnt++; x/=2;}
	for (int i = 3; i <= x / i; i += 2)
		while (x % i == 0) {cnt++; x/=i;}

	if (x > 2) cnt++;

	return cnt;
}

int main()
{

	ios::sync_with_stdio(0);
	cin.tie(0);
	
	IN(int, t);
	while (t--) {
		IN(ll, x);
		IN(ll, y);

		ll g = gcd(x, y);
		x /= g;
		y /= g;

		if (!isPerfect(x) || !isPerfect(y)) {
			cout << -1 End;
			continue;
		}

		cout << factorize(sqrt(x)) + factorize(sqrt(y)) End;
	}

}