# include <bits/stdc++.h>
using namespace std;
# define rep(i,a,n) for (int i=a; i<=n; ++i)
# define per(i,a,n) for (int i=a; i>=n; --i)
# define bug puts("H");
# define pb push_back
# define mp make_pair
# define all(x) (x).begin(), (x).end()
# define fi first
# define se second
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mem(a,b) memset(a,b,sizeof(a))
# define INF 1000000001
# define MOD 998244353
typedef vector<int> Vi;
typedef long long i64;
typedef long long ll;
typedef pair<int, int> Pi;
//i64 powmod(i64 a, i64 b, i64 mod){i64 res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//i64 Inv(i64 b){return powmod(b,(i64)MOD-2);}
inline int Scan() {
    int x=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x;
}
const int N = 1005;
//const int M = 524288;
const double eps = 1e-9;


int dp[N][N];

int main ()
{
    int T;
    scanf("%d", &T);
    rep(i,1,1000) rep(j,1,1000) {
        if (i==1 && j==1) dp[i][j] = 1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (__gcd(i,j) == 1);
    }
    while (T--) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", dp[x][y]);
    }
    return 0;
}