#include<bits/stdc++.h>
using namespace std;

int f[1010][1010];
int t,n,m;

inline int rd()
{
    int x=0;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar());
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

inline int gcd(int x,int y) { return (!y)?x:gcd(y,x%y); }

inline void pre_gao()
{
    for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++)
    {
        f[i][j]=max(f[i-1][j],f[i][j-1])+(gcd(i,j)==1);
    }
}

int main()
{
    t=rd();pre_gao();
    while (t--)
    {
        int x=rd(),y=rd();
        printf("%d\n",f[x][y]);
    }
    return 0;
}