#include<bits/stdc++.h>
#define LL long long
#define rint register int
using namespace std;bool f1;
int T,n,m,f[1010][1010];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
bool f2;int main(){
//    printf("%.2lf\n",(&f2-&f1)/1024.0/1024);
    for(int i=1;i<=1005;i++){
        for(int j=1;j<=1005;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(gcd(i,j)==1)f[i][j]++;
        }
    }
    cin>>T;
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%d\n",f[n][m]);
    }
    return 0;
}