#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define sz(a) ((int) (a).size())
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define vi vector<int>
#define ull unsigned long long
#define i128 __int128
using namespace std;
#define pii pair<int,int>
const int N = 1.2e6 + 7;
ll n, m;
map<pair<ll,ll>,int>mp;
ll calc(ll x, ll y) {
	ll G = __gcd(x, y);
	x /= G;
	y /= G;
	if(x > y) swap(x, y);
	ll ans = x + 1;
	if(ans == 0) return ans;
	if(x == 0 || y == 0) return 1;
	if(mp.count({x, y})) return mp[make_pair(x, y)];
	L(g, 2, min(x, y)) {
		ans = min(ans, x % g + y % g + calc(x / g, y / g));
	}
	return mp[make_pair(x, y)] = ans;
}
void Main() {
	cin >> n >> m;
	cout << calc(n, m) << '\n';
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
}
/*
1
10000 99999
*/