#include<bits/stdc++.h>
using namespace std;
const int M=1005;
int f[M][M];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void init(){
    for(int i=1;i<=1e3;++i)for(int j=1;j<=1e3;++j)
        f[i][j]=max(f[i-1][j],f[i][j-1])+(gcd(i,j)==1);
}
int main(){
    init();
    int t;scanf("%d",&t);
    for(int a,b;t;--t){
        scanf("%d%d",&a,&b);
        printf("%d\n",f[a][b]);
    }
    return 0;
}