#include<bits/stdc++.h>
#define LL long long
#define Max(a,b) ((a<b)&&(a=b))
#define Min(a,b) ((a>b)&&(a=b))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=hd[a],y;(y=to[i]);i=nxt[i])
using namespace std;
char C;
inline int rd() {
    int res=0,f=1;
    while(C=getchar(),C<48||C>57)if(C=='-')f=0;
    do res=(res<<3)+(res<<1)+(C^48);
    while(C=getchar(),C>=48&&C<=57);
    if(f)return res;
    return -res;
}
int dp[1005][1005];
void init(){
    rep(i,1,1000)rep(j,1,1000){
        int t=(__gcd(i,j)==1);
         dp[i][j]=max(dp[i-1][j],dp[i][j-1])+t;
    }
}
int main() {
    int T=rd();
    init();
    while(T--)printf("%d\n",dp[rd()][rd()]);
}