#include <stdio.h>

int main(){
    unsigned long long int a,b;
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%lld %lld",&a,&b);
        unsigned long long int count = 0;
        while (a != 0 && b != 0){
            if (a > b){
                a = a - b;
                count++;
            }
            else{
                b = b - a;
                count++;
            }
        }
        printf("%lld\n",count);
    }
    return 0;    
}