#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
const ll inf=LLONG_MAX/4;
#define rep2(i,j,k) for(ll i=ll(j);i<ll(k);i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i,k) rrep2(i,k,0)
#define eb emplace_back
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
template<class T>
bool chmin(T& a, T b){return a>b ? a=b,1:0;}
template<class T>
bool chmax(T& a, T b){return a<b ? a=b,1:0;}

#define ln "\n"

void solve(){
	ll a,b; cin>>a>>b;
	vl B(a+1), dp(a+1,inf);
	dp[a]=0;
	B[a]=b;
	rrep(now,a+1){
	//	cout << now << " " << B[now] << " " << dp[now] << endl;
		if(now == 0){
			if(B[0]) dp[0]++;
			continue;
		}
		ll nb = B[now];
		while(nb%now){
			ll G=gcd(nb,now);
			if(chmin(dp[now-G],dp[now]+1)){
				B[now-G]=nb;
			}
			nb -= G;
			dp[now]++;
		}
		{
			ll G=gcd(nb,now);
			if(chmin(dp[now-G],dp[now]+1)) B[now-G]=nb;
		}
		dp[now]+=nb/now;
		dp[now]++;
	}
	ll ans=*min_element(all(dp));
	cout << ans << ln;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	ll t; cin>>t;
	while(t--) solve();
}