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

int main(){
    int T,n,m; scanf("%d",&T);
    while (T--){
       int ans=0;
       scanf("%d%d",&n,&m);
       while (m){
          if (m<n) swap(m,n);
          m-=n; ++ans;
       }
       printf("%d\n",ans);
    }
    return 0;
}