#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;
	ll ans=inf;
	vector<map<ll,ll>> dp(a+1);
	dp[a][b]=0;
	rrep(na,a+1){
		if(na == 0){
			for(auto el: dp[na]) chmin(ans, el.second + (el.first ? 1 : 0));
			continue;
		}
		dp[na][0] = inf;
		while(true){
			auto el = *(dp[na].rbegin());
			ll nb=el.first;
			if(nb == 0){
				chmin(ans, el.second+1);
				break;
			}
//			cout << na << " " << nb << " " << el.second << endl;
			dp[na].erase(nb);
			if(nb%na){
				nb -= gcd(nb,na);
				if(!dp[na].count(nb)) dp[na][nb]=el.second+1;
				else chmin(dp[na][nb], el.second+1);
			}
			else{
				chmin(dp[na][0], el.second+el.first/na);
			}
			ll nxa = na-gcd(na,el.first);
			if(!dp[nxa].count(el.first)) dp[nxa][el.first]=el.second+1;
			else chmin(dp[nxa][el.first], el.second+1);
		}
	}
	cout << ans << ln;
}

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