#include<bits/stdc++.h>
#define ls ch[x][0]
#define rs ch[x][1]
#define ll long long
using namespace std;

inline ll read(){
    ll num=0,neg=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')neg=-1;c=getchar();}
    while(isdigit(c)){num=(num<<3)+(num<<1)+c-'0';c=getchar();}
    return num*neg;
}

int f[1010][1010],T;

inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}

int main(){
    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])+(gcd(i,j)==1);
    }
    
    T=read();
    while(T--)
    {
        int x=read(),y=read();
        printf("%d\n",f[x][y]);
    }return 0;
}