#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int x,y;
    int sum;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        sum=1;
        scanf("%d%d",&x,&y);
        while(x!=y)
        {
            if(x>=y)
            {
                x=x-y;
                sum++;
            }
            else 
            {
                y=y-x;
                sum++;
            }
        }
        printf("%d\n",sum);
    }
}