/*********************************************************************
    Problem:1003
    Author:hydd
    Date:
*********************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int T,a,b,dp[2100][2100];
int gcd(int a,int b){
    if (!b) return a;
    return gcd(b,a%b);
}
int dfs(int a,int b){
    if (a==0||b==0) return 0;
    if (~dp[a][b]) return dp[a][b];
    dp[a][b]=max(dfs(a-1,b),dfs(a,b-1))+(gcd(a,b)==1);
    return dp[a][b];
}
int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&a,&b);
        printf("%d\n",dfs(a,b));
    }
    return 0;
}