#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
int main()
{
    int t,n,m,num,tmp,sum;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n>m)
        {
            tmp=n;
            n=m;
            m=tmp;
        }
        sum=n*m;
        num=0;
        while(sum!=0)
        {
            if(sum>=n*n)
            {
                sum-=n*n;
                m-=n;
                num++;
                sum=n*m;
                if(n>m)
                {
                    tmp=n;
                    n=m;
                    m=tmp;
                }
            }
        }
        cout<<num<<endl;
    }
    return 0;
}