#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        int cnt=0;
        while(n&&m){
            if(n>m)swap(n,m);
            m-=n;
            cnt++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}