#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1e18;

int T;
ll res[4010][4010];

struct state{
	ll a,b;
	int move;
};
queue<state> q;

int bfs(ll a,ll b){
	q=queue<state>();
	q.push({a,b,0});
	while(!q.empty()){
		int A=q.front().a,B=q.front().b,m=q.front().move;
		q.pop();
		if(A==0||B==0){
			return m+1;
		}
		ll gcd=__gcd(A,B);
		q.push({A-gcd,B,m+1});
		q.push({A,B-gcd,m+1});
	}
	return -1;
}

int main(){
	ios::sync_with_stdio(0);
	
	cin>>T;
	while(T--){
		ll a,b;
		cin>>a>>b;
		cout<<bfs(a,b)<<endl;
	}
	
	
	return 0;
}