#include <cstdio>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
int n,m,T;
int ans;
int f[1020][1020];
int gcd(int x,int y){
    if(x<y)swap(x,y);
    while(x % y){
        int z= x%y;
        x =y ;
        y = z;
    }
    return y;
}
int get(){
    char t=getchar();
    while(t<'0'||t>'9')t=getchar();
    int x = 0;
    while(t>='0'&&t<='9'){
        x*=10;
        x+=t-'0';
        t=getchar();
    }
    return x;
}
int main()
{
    T = get();
    f[1][1]=0;
    for(int i=1;i<=1000;++i)
        for(int j=1;j<=1000;++j){
            if(gcd(i,j) == 1)++f[i][j];
            f[i+1][j] = max(f[i+1][j],f[i][j]);
            f[i][j+1] = max(f[i][j],f[i][j+1]);
        }
    for(int ii=1;ii<=T;++ii){
        n = get();
        m = get();
        printf("%d\n",f[n][m]);
    }
    return 0;
}