#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int getint()
{
    int res=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')
        ch=getchar();
    while('0'<=ch && ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res;
}
void f()
{
    m=getint();
    int ans=0;
    while(n && m)
    {
        if(n<m)
            swap(n,m);
        n-=m;
        ans++;
    }
    printf("%d\n",ans);
}
int main()
{
    int T=getint();
    while((scanf("%d",&n))!=EOF)
        f();
    return 0;
}