#include<bits/stdc++.h>
using namespace std;
int T,i,j;
int f[1010][1010];
main()
{
    cin>>T;
    for(i=1;i<=1000;i++)for(j=1;j<=1000;j++)
    {
        if(i>1)f[i][j]=max(f[i][j],f[i-1][j]);
        if(j>1)f[i][j]=max(f[i][j],f[i][j-1]);
        f[i][j]+=(__gcd(i,j)==1);
    }
    while(T--)
    {
        scanf("%d%d",&i,&j);
        printf("%d\n",f[i][j]);
    }
}