#include<bits/stdc++.h>
using namespace std;
int n,c,b;
int r(int y,int z){
	int x=0;
	while(y>0&&z>0){
		if(y>z){
			y=y-z;
			x++;
		}else{
			z=z-y;
			x++;
		}
	}
	return x;
}
int main(){
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>b>>c;
		a[i]=r(b,c);
	}
	for(int j=0;j<n;j++){
		cout<<a[j]<<endl; 
	}
}