#pragma comment(linker, "/stack:200000000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define debug(x) cout << #x" = " << x << endl;
#define pp(x,y) cout << "pp: " << x << " " << y << endl;
inline ll read(){
    register ll x=0,f=1;register char c=gc();
    for(;!isdigit(c);c=gc())if(c=='-')f=-1;
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void wri(ll x){write(x);pc(' ');}
void writeln(ll x){write(x);pc('\n');}
const int mod = 998244353;
const int maxn = 1e7+233;
int f[1005][1005];
void solve(){
    int a = read(),b = read();
    writeln(f[a][b]);
}
int main(){
    f[1][1] = 1;
    Rep(a,1,1000){
        Rep(b,1,1000){
            f[a+1][b] = max(f[a+1][b],f[a][b]+(__gcd(a+1,b)==1));
            f[a][b+1] = max(f[a][b+1],f[a][b]+(__gcd(a,b+1)==1));
        }
    }
    int T = read();
    while(T--) solve();
}