#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int sum(int m, int n)
{
    if(m < n)
        swap(m, n);
    if(n == 0)
        return 0;
    return m/n + sum(m%n, n);
}


int main()
{
    int T;

    scanf("%d", &T);

    while(T--)
    {
        int m, n;

        scanf("%d%d", &m, &n);

        printf("%d\n", sum(m, n));
    }

    return 0;
}