#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<cctype>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

int main() {
   int t; scanf("%d",&t);
   while(t--) {
    int n, m; scanf("%d%d",&n, &m);
    if(n > m) {
        swap(n, m);
    }
    int sum = 0;
    while(n * m != 0) {
        sum += m / n;
        int tmp = n;
        n = m % n;
        m = tmp;
        if(n > m) {
            swap(n, m);
        }
    }
    printf("%d\n", sum);
   }
   return 0;
}