#include <bits/stdc++.h>   using namespace std;   int a, b, m[1000];   int s = 0;   int main() {     int n;     cin >> n;     int z = n;     while (n > 0) {       s = 0;       cin >> a >> b;       while (a > 0 && b > 0) {         if (a >= b) {           int t = a / b;           a = a % b;           s += t;         } else {           int t = b / a;           b = b % a;           s += t;         }       }       m[z - n + 1] = s;       --n;     }     int j;     for (j = 1; j <= z; ++j) cout << m[j] << endl;   }   