#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int tes,n,m,f[1005][1005];
int read(){
    int res=0,op=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')op=-1;ch=getchar();}
    while(isdigit(ch))res=res*10+ch-'0',ch=getchar();
    return res*op;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
void prework(){
    for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++)
        f[i][j]=max(f[i][j-1],f[i-1][j])+(__gcd(i,j)==1);
}
void solve(){
    n=read();m=read();
    if(n<m)swap(n,m);
    printf("%d\n",f[n][m]);
}
int main()
{
    prework();
    tes=read();
    while(tes--)solve();
    return 0;
}