#include <iostream>
#include <cmath>
#include <vector>
#include <string.h>
#include <bits/stdc++.h>
#include <cstdlib>
#include <time.h>
#include <fstream>
#include <iterator>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>

using namespace std;

#define ll long long
#define ull unsigned ll
#define ld long double
typedef vector<int> vi;
typedef multiset<int> mi;
typedef multiset<ll> mll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<int>> _2vi;
typedef vector<vector<ll>> _2vll;
#define all(v) ((v).begin()), ((v).end())
#define sz(v) ((ll)((v).size()))

#define vinp(v, n)                \
    for (ull i = 0; i < (n); i++) \
    cin >> (v)[i]
#define printv(v)      \
    for (auto i : (v)) \
    cout << i << " "
#define fr0(i, n) for (ull(i) = 0; (i) < (n); (i)++)
#define fr1(i, n) for (ull(i) = 1; (i) < (n); (i)++)
#define fr(i, x, n) for (ull(i) = (x); (i) < (n); (i)++)
#define _CRT_SECURE_NO_WARNING
const ll MOD = 1000000007;

void Bustany() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("./in.txt", "r", stdin), freopen("./out.txt", "w", stdout);
#endif
}


ll fac(ull n){
    ll f=0;
    for (ll i = 2; i*i <= n; i++) {
        while (n > 0 && n % i == 0) {
            f++;
            n /= i;
        }
    }
    return f;
}


void solve() {
    ll a, b;
    cin >> a >> b;
    if (b > a)swap(a, b);
    if (a % b != 0) {
        cout << -1 << '\n';
        return ;
    }
    ull ans = a / b;
    if ((ull)((ull)(sqrt(ans)* (ull)sqrt(ans)))!=ans) {
        cout << -1 << '\n';
        return ;
    }
    cout << fac(sqrt(ans)) << '\n';

//    logx(y) = log10(y) / log10(x)

}

int main() {
    Bustany();
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();

    }
}