#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        int ans = 0;
        while (n && m)
        {
            ans++;
            if (n == m)
            {
                n = 0;
                m = 0;
            }
            else
            {
                if (n > m)
                {
                    n -= m;
                }
                else
                {
                    m -= n;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}