//
//  main.cpp
//  bc75.1
//
//  Created by eycia on 16/3/12.
//  Copyright © 2016年 eycia. All rights reserved.
//

#include <cstdio>

int main(int argc, const char * argv[]) {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
    
        int tot = 0;
        while (n > 0 && m > 0) {
            if (n >= m) {
                n -= m;
                tot++;
            } else if (m > n) {
                m -= n;
                tot++;
            }
        }
        
        printf("%d\n", tot);
    }
}