Ta dễ nhận ra số lần thực hiện thao tác cắt cho đến khi ~A < B~ là ~\frac{A}{B}~ , sao đó chỉ cần đổi giá trị ~A~ và ~B~ với nhau . Nói tóm lại ta chỉ cần thực hiện hai thao tác

• Tính số lần cắt bằng cách lấy ~\frac{A}{B}~ ,thực hiện trừ ~A~ đi một khoảng.
• Nếu ~A < B~ thì hoán đổi hai giá trị ~A~ và ~B~

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void minimize(long long &x,long long y){
   if(x>y){
      x=y;
   }
}

void maximize(long long &x,long long y){
    if(x<y){
        x=y;
    }
}

template <typename T> inline void read(T & x)
{
    char c; bool nega=0;
    while((!isdigit(c=getchar()))&&c!='-');
    if(c=='-')
    {
        c=getchar();
        nega=1;
    }
    x=c-48;
    while(isdigit(c=getchar()))
    {
        x=x*10+c-48;    
    }
    if(nega) x=-x;
}
template <typename T> void Write(T x) {if (x > 9) Write(x/10); putchar(x%10+48);}
template <typename T> void write(T x) {if (x < 0) {putchar('-'); x = -x;} Write(x);}

long long pow_mod(long long a, long long b, long long m) {
     long long res = 1;
     while(b){
            res = res * (b & 1 ? a : 1) % m;
            a = a * a % m; b >>= 1;
     }
     return res;
}

long long GCD(long long a , long long b){
    while(b != 0 ){
         a = a % b;
         long long tmp = a;
         a = b;
         b = tmp;
    }
    return a;
}

long long minn(long long a ,long long b , long long c ,long long d){
    long long res = a;
    if(res > d) res = d;
    if(res > b) res = b;
    if(res > c) res = c;
    return res;
}
ll LCM(ll a , ll b){
    return a * b / GCD(a , b);
}
const int INF = 1e9 + 7;
const ll MAXN = 2e5 + 7;
ll t;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while(t--){
        ll a , b;
        cin >> a >> b;

        ll res = 0;
        while (a != b) { if (a > b) a -=b; else b -= a; ++res; }

        cout << res << '\n';
    }
   return 0;
}