#include<bits/stdc++.h>
#define maxn 1050
using namespace std;

int dp[maxn][maxn];

int gcd(int a,int b)    {
    return b?gcd(b,a%b):a;
}

const int inf=1e9;

int calc(int a,int b)   {
    if (!a||!b) return -inf;
    if (dp[a][b]) return dp[a][b];
    if (a==1&&b==1) return dp[a][b]=1;
    dp[a][b]=max(calc(a-1,b),calc(a,b-1))+(gcd(a,b)==1);
    // cout<<a<<" "<<b<<":"<<dp[a][b]<<endl;
    return dp[a][b];
}

int main()  {
    int T;
    scanf("%d",&T);
    while (T--) {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",calc(a,b));
    }
    return 0;
}