#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define pi acos(-1.0)
#define lowbit(x) x&(-x)
using namespace std;

int T,a,b,f[1010][1010];

void init(){
    for(int i=1;i<=1000;i++) f[1][i]=i;
    for(int i=2;i<=1000;i++){
        for(int j=i;j<=1000;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1])+(__gcd(i,j)==1?1:0);
        }
    }
}

int main(void){
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&a,&b);
        if(a>b) swap(a,b);
        printf("%d\n",f[a][b]);
    }
    return 0;
}