/*CODED BY mahmudulsakib2019
  DATE:-06/3/2024;TIME:-07:39 pm
  BANGALDESH , SYLHET*/

#include <iostream>
#include <cmath>     ///mathematics
#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
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        unsigned long long a, b;
        cin >> a >> b;
        int count = 0;
        while (a != 0 && b != 0) {
            unsigned long long step_1 = max(a, b);
            if (step_1 == a) {
                a = a - b;
                count = count + 1;
            } else if (step_1 == b) {
                b = b - a;
                count = count + 1;
            }
        }
        cout << count << endl;
    }
    return 0;
}