#include <bits/stdc++.h>   using namespace std;   class subtractions {    private:     int _a, _b;     int _operations;     bool even_divide(int& a, int& b) {       if (b > a && !(b % a)) {         _operations += (b / a);         return true;       } else if (a >= b && !(a % b)) {         _operations += (a / b);         return true;       }       return false;     }     bool quick_divide(int& a, int& b) {       if (b > a) {         int factor = b / a;         b -= a * factor;         _operations += factor;         return true;       } else if (a >= b) {         int factor = a / b;         a -= b * factor;         _operations += factor;         return true;       }       return false;     }       public:     subtractions(int a = 0, int b = 0) : _a(a), _b(b) { _operations = 0; }     int operate() {       while (_a > 0 && _b > 0) {         if (even_divide(_a, _b)) break;         if (quick_divide(_a, _b)) continue;         ++_operations;       }       return _operations;     }   };   int main() {     int tests = 0;     cin >> tests;     while (tests > 0) {       int a, b;       cin >> a >> b;       subtractions s(a, b);       cout << s.operate() << endl;       --tests;     }     return 0;   }   