#include<bits/stdc++.h>
typedef int LL;
typedef double dl;
#define opt operator
#define pb push_back
const LL maxn=1e6+9,mod=998244353,inf=0x3f3f3f3f;
LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
    }return x*f;
}
void Chkmin(LL &x,LL y){
    if(y<x) x=y;
}
void Chkmax(LL &x,LL y){
    if(y>x) x=y;
}
LL add(LL x,LL y){
    return x+=y,x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
    return x-=y,x<0?x+mod:x;
}
LL mul(LL x,LL y){
    return 1ll*x*y%mod;
}
LL Gcd(LL a,LL b){
    return b?Gcd(b,a%b):a;
}
LL f[1001][1001];
int main(){
    f[1][1]=1;
    for(LL i=1;i<=1000;++i){
        for(LL j=1;j<=1000;++j){
            Chkmax(f[i+1][j],f[i][j]+(Gcd(i+1,j)==1));
            Chkmax(f[i][j+1],f[i][j]+(Gcd(i,j+1)==1));
        }
    }
    LL T=Read();
    while(T--){
        LL a(Read()),b(Read());
        printf("%d\n",f[a][b]);
    }
    return 0;
}