#pragma warning(disable:4996)
#include <cstdio>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <iostream>
#include <stack>
#include <assert.h>
//#pragma comment(linker, "/STACK:202400000,202400000") //不需要申请系统栈
using namespace std;


int main()
{
    int t, i, j, n, m, cy, tp, ans;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &m);
        if (n > m)
        {
            cy = n;
            n = m;
            m = cy;
        }
        ans = 0;
        while (m && n)
        {
            ans += m / n;
            m -= m / n*n;
            cy = n;
            n = m;
            m = cy;
        }
        printf("%d\n", ans);
    }
    return 0;
}