#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int t,n,m,i,j,dp[1005][1005],x,y;
int main(){
    scanf("%d",&t);
    for(i=1;i<=1000;++i)
        for(j=1;j<=1000;++j)
            if(i==1||j==1)
                dp[i][j]=max(i,j);
            else
                dp[i][j]=max(dp[i][j-1],dp[i-1][j])+(__gcd(i,j)==1);
    while(t--)
    {
        scanf("%d %d",&x,&y);
        printf("%d\n",dp[x][y]);
    }
}