#include <cstdio>
#include <algorithm>

const int MN = 1005;

int f[MN][MN];
void Init(int N) {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            f[i][j] = f[i - 1][j] < f[i][j - 1] ? f[i][j - 1] : f[i - 1][j];
            f[i][j] += std::__gcd(i, j) == 1;
        }
    }
}

int main() {
    Init(1000);
    int Tests;
    scanf("%d", &Tests);
    while (Tests--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", f[a][b]);
    }
    return 0;
}