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

int n, g[1010][1010], f[1010][1010];

int main(){
    n=1000;
    memset(g,-1,sizeof g);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j){
            f[i][j]=max(f[i][j-1],f[i-1][j])+(__gcd(i,j)==1);
        }
    int T, a, b;
    for (cin>>T;T--;){
        scanf("%d%d",&a,&b);
        printf("%d\n",f[a][b]);
    }
}