#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        long long n,m;
        scanf("%I64d%I64d", &n, &m);
        int ans = 0;
        while(n!=0 && m!=0){
            if(n>m) swap(n,m);
            ans += m/n;
            m %= n;
        }
        printf("%d\n", ans);
    }
    return 0;
}