#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int maxn = 1010;
int dp[1010][1010];

int GCD(int x,int y){return (x == 0) ? y : GCD(y % x, x);}
void work(){
    for (int i=1;i<=1000;i++) {dp[1][i] = i; dp[i][1] = i;}
    for (int i=2;i<=1000;i++){
        dp[i][i] = dp[i-1][i];
        for (int j=i+1;j<=1000;j++){
            int gcd = GCD(i,j);
            dp[i][j] = max(dp[i-1][j], dp[i][j-1] ) + (gcd == 1);
        }
    }
}
void vgeler(){
    work();
    int test,a,b;
    scanf("%d",&test);
    while (test--){
        scanf("%d%d",&a,&b);
        if (a > b) swap(a,b);
        printf("%d\n",dp[a][b]);
    }
}
int main(){
    vgeler();
    return 0;
}