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

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int f[1010][1010];

inline int gcd(int a,int b){
    while(b){
        int r=a%b;a=b;b=r;
    }
    return a;
}

int main(){
    f[1][1]=1;
    for(int i=2;i<=1000;i++)f[i][1]=f[1][i]=i;
    for(int i=2;i<=1000;i++)
    for(int j=2;j<=1000;j++)
    if(gcd(i,j)==1) f[i][j]=max(f[i][j-1],f[i-1][j])+1;
    else f[i][j]=max(f[i][j-1],f[i-1][j]);
    for(int tt=read();tt;tt--){
        int a=read();int b=read();
        printf("%d\n",f[a][b]);
    }
}