/*CODED BY mahmudulsakib2019
  DATE:-12/03/2024;TIME:-16:10 pm
  BANGALDESH , SYLHET*/

#include <iostream>
#include <cmath>     ///mathematics
#include<cstdlib>    ///for std::exit(EXIT_SUCCESS)
#include <vector>    ///array
#include <regex>     ///searching_prefix_suffix
#include <algorithm> ///finding_max_min_from_array
#include <string>    ///string_manipulation
#include <numeric>   ///findin total sum of an array
#include<bits/stdc++.h>
using namespace std;

int main() {
    int T;
    std::cin >> T;
    while(T--) {
        long long A, B;
        std::cin >> A >> B;
        int count = 0;
        while(A != 0 && B != 0) {
            if(A > B) {
                count += A / B;
                A %= B;
            } else {
                count += B / A;
                B %= A;
            }
        }
        std::cout << count << std::endl;
    }
    return 0;
}