#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clrmax(x) memset(x,0x3f3f3f3f,sizeof(x))
#define clrmin(x) memset(x,-0x3f3f3f3f,sizeof(x))
#define pb push_back
#define LL long long
#define mod 1000000007
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
const int N = 1e3+10;
const int M = 1e6+10;
int n,m,T;
int dp[N][N];
int main(){
    scanf("%d",&T);
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            if(i == 1 && j == 1) dp[1][1] = 1;
            else if(i == 1) dp[i][j] = dp[i][j-1] + (__gcd(i,j) == 1 ? 1 : 0);
            else if(j == 1) dp[i][j] = dp[i-1][j] + (__gcd(i,j) == 1 ? 1 : 0);
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + (__gcd(i,j) == 1 ? 1 : 0);
            }
        }
    }
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%d\n",dp[n][m]);
    }
    return 0;
}