#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int n, m, T, ans;

int main()
{
    scanf("%d", &T);
    while(T > 0)
    {
        T--;
        ans = 1;
        scanf("%d%d", &n, &m);
        while(n != m)
        {
            int p;
            p = min(n, m);
            n = abs(n - m);
            m = p;
            ans++;
        }
        printf("%d\n", ans);
    }
}