#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;
}
