#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        int ans=0;
        scanf("%d%d",&n,&m);
        for(;;)
        {
            
            int yy=max(n,m)/min(n,m);
            int xx=max(n,m)-min(n,m)*yy;
            ans+=yy;
            if(xx==0)
            break;
            if(max(n,m)!=min(n,m))
            {
                if(max(n,m)==n)
                {
                    n=n-m*yy;
                    continue;
                }
                if(max(n,m)==m)
                {
                    m=m-n*yy;
                    continue;
                }
            }
            else
            {
                m=m-n*yy;
            }
        }    
        printf("%d\n",ans);
    }
    return 0;
}