#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int gcd(int x,int y){
    if(!y)return x;
    return gcd(y,x%y);
}
int dfs(int x,int y){
    if(x==1&&y==1)return 1;
    if(dp[x][y]!=-1)return dp[x][y];
    int ans=0;
    if(x!=1)ans=max(ans,dfs(x-1,y));
    if(y!=1)ans=max(ans,dfs(x,y-1));
    ans+=gcd(x,y)==1;
    return dp[x][y]=ans;
}
int main(){
    memset(dp,-1,sizeof(dp));
    int T;
    cin>>T;
    int n,m;
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%d\n",dfs(n,m));
    }
    return 0;
}