//
//  main.cpp
//  A
//
//  Created by 黄宇凡 on 16/3/12.
//  Copyright © 2016年 黄宇凡. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;



int main(int argc, const char * argv[]) {
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n<m) swap(n,m);
        int cnt=0;
        while(m>0){
            cnt+=n/m;
            n=n%m;
            if(n<m) swap(n,m);
        }
        cout<<cnt<<endl;
    }
    return 0;
}