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

#define int long long
#define debug(x) cout<<#x<<" "<<x<<endl;

const int N=1e6+5;
const double eps=1e-9;
const int INF=1e18;

int f[1005][1005];

signed main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(__gcd(i,j)==1){
                f[i][j]++;
            }
        }
    }
    int t;cin>>t;
    while(t--){
        int x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld\n",f[x][y]);
    }
    return 0;
}

//Created Time  :2020/7/19 14:12:10