#include <cstdio>
#include <algorithm> 
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
void init(){
    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++){
            if(i == j && i == 1) continue;
            dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]) + (__gcd(i,j) == 1);
        }
    }
}
int main(){
    init();
    int t;scanf("%d",&t);
    while(t--){
        int a,b;scanf("%d%d",&a,&b);
        printf("%d\n",dp[a][b]);
    }
}