#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e3+10;
int dp[N][N];
int dfs(int x,int y){
    if(x==1&&y==1)    return dp[x][y]=1;
    if(dp[x][y])    return dp[x][y];
    int res=0,mx=0; if(__gcd(x,y)==1) res=1;
    if(x>1)    mx=max(mx,dfs(x-1,y));
    if(y>1)    mx=max(mx,dfs(x,y-1));
    return dp[x][y]=res+mx;
}
signed main(){
    dfs(1e3,1e3);
//    for(int i=1;i<=10;i++){
//        for(int j=1;j<=10;j++){
//            cout<<dp[i][j]<<' ';
//        }puts("");
//    }
    int T; cin>>T; while(T--){
        int x,y; scanf("%d %d",&x,&y); printf("%d\n",dp[x][y]);
    }
    return 0;
}