#include <bits/stdc++.h>

#define int int64_t
using namespace std;

const int MN = 5004;
int dp[MN][MN];
const int inf = 1e18;

void solve() {
	int a,b;
	cin>>a>>b;
	int gg = __gcd(a,b);
	for(int i=0; i<MN; ++i) dp[i][0]=1;
	dp[0][0]=0;

	for(int g=a; g>=gg; --g) {
		for(int aog=1; g*aog<=a; ++aog) {
			int ca = aog*g;
			int cb = b-(b%g);
			dp[g][aog]=dp[g][aog-1]+1;
			for(int g2=g+g; g2<=ca; g2+=g) if(ca%g2==0) {
				/*for(int aog2=0; g2*aog2<=ca; ++aog2) {
					int a2 = g2*aog2;
					int d = (ca-a2)/g + (cb%g2)/g;
					dp[g][aog] = min(dp[g][aog], d+dp[g2][aog2]);
				}*/
				int aog2 = ca/g2;
				int d = (cb%g2)/g;
				dp[g][aog] = min(dp[g][aog], d+dp[g2][aog2]);
			}
			if(__gcd(ca,cb)!=g) dp[g][aog]=dp[__gcd(ca,cb)][ca/__gcd(ca,cb)];//inf;
			//cerr<<"dp["<<g<<"]["<<aog<<"]= "<<dp[g][aog]<<'\n';
		}
	}

	cout<<dp[gg][a/gg]<<'\n';
}

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}