#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e3 + 100;

int G[N][N], dp[N][N];

int gcd(int a, int b) {
    if (G[a][b]) return G[a][b];
    if (b == 0) G[a][b] = G[b][a] = a;
    else G[a][b] = G[b][a] = gcd(b, a % b);
    return G[a][b];
}

int f(int a, int b) {
    if (gcd(a, b) == 1) return 1;
    return 0;
}

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

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