#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=1010;
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
int g[maxn][maxn];
int dp[maxn][maxn];
int T,n,m;
inline int dec(int x,int d){
    return x-d>=1?x-d:1;
}
int main(){
    for(int i=1;i<maxn;i++){
        for(int j=1;j<maxn;j++){
            g[i][j]=gcd(i,j);
        }
    }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<maxn;i++)dp[i][1]=i;
        for(int i=1;i<maxn;i++)dp[1][i]=i;
        for(int i=2;i<maxn;i++){
            for(int j=2;j<maxn;j++){
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                dp[i][j]+=(g[i][j]==1);
            }
        }
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        scanf("%d%d",&n,&m);
        printf("%d\n",dp[n][m]);
    }
    
    return 0;
}