#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
    for(int i=1;i<=1000;i++)dp[i][1]=dp[1][i]=i;
    for(int i=2;i<=1000;i++){
        for(int j=2;j<=1000;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+(__gcd(i,j)==1);
        }
    }
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",dp[a][b]);
    }
}