#include <cmath>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>


using namespace std;


int main (void)
{
    int t, m, n, T, cnt;

    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&m,&n);
        if(m < n)
        {
            t = m;
            m = n;
            n = t;
        }

        if(m != 1)
            cnt = 0;
        else
            cnt = 1;


        while(1)
        {
            if(m == n)
            {
                cnt = 1;
                break;
            }
            if( (n == 0) || ((m == 1 || m == 0) && (n == 1 || n == 0)))
                break;
            cnt = cnt + m/n;
            m = m%n;
            if(m < n)
            {
                t = m;
                m = n;
                n = t;
            }

        }
        printf("%d\n",cnt);
    }

    return 0 ;
}