#include <bits/stdc++.h>   using namespace std;   pair<int, int> p;   void sort() {     int temp = 0;     if (p.first < p.second) {       temp = p.first;       p.first = p.second;       p.second = temp;     }   }   int main() {     int n;     cin >> n;     for (int i = 0; i < n; i++) {       int op = 0;       cin >> p.first >> p.second;       if (p.first == p.second)         op = 1;       else {         if (p.first % p.second == 0)           op = p.first / p.second;         else {           while (p.first % p.second != 0) {             sort();             op += p.first / p.second;             p.first = p.first % p.second;           }         }       }       cout << op << endl;     }     return 0;   }   