#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int T,m,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int ans=0;
        while(1)
        {
            if(m<n)
            {
                n-=m;
                ans++;
            }
            else if(m>n)
            {
                m-=n;
                ans++;
            }
            else
            {
                ans++;
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}