#include <cstdio>
#include <algorithm>

using namespace std;

int solve(int x,int y){
    if (x==0) return 0;
    return y/x+solve(y % x,x);    
}
int T,x,y;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&x,&y);
        printf("%d\n",solve(x,y));
    }
}