#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define PI acos(-1.0)
#define F first
#define S second
#define pb push_back
#define debug(x); printf("debug%d\n",x);
#define des(x); printf("des:%s\n",x+1);
#define rep(f,t) for(int i=f;i<=t;i++)
const ll INF=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=998244353;
using namespace std;
int t;
int a,b;
int check[1010][1010];
int ans[1010][1010];
bool isCoprime(int x,int y)
{
    if(x==1 && y==1)//1和1互质
        return true;
    else if(x<=0 || y<=0 || x==y)//非正整数都不存在互质的说法
        return false;
    else if(x==1 || y==1)//1和任何正整数都互质
        return true;
    else
    {
        int tmp=0;
        //使用求商判断法，如果输入的x<y，第一次循环会交换x和y的位置
        while(true)
        {
            tmp=x%y;
            if(tmp==0)
            {
                break;
            }
            else
            {
                x=y;
                y=tmp;
            }
        }
        if(y==1)          //最大公约数为1,所以互质
            return true;
        else              //最大公约数大于1，所以不互质
            return false;
    }
}
int main()
{
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            if(isCoprime(i,j))
            {
                check[i][j]=1;
            }
        }
    }
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            ans[i][j]=max(ans[i-1][j],ans[i][j-1])+check[i][j];
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);

        printf("%d\n",ans[a][b]);
    }
    return 0;
}