#include <bits/stdc++.h>
using namespace std;
int T, a, b, f[1005][1005];
int gcd(int x, int y) {
    int r = x % y;
    while (r) x = y, y = r, r = x % y;
    return y;
}
int main() {
    scanf("%d", &T);
    memset(f, 0, sizeof f);
    for (int i = 1; i <= 1000; i++)
        for (int j = 1; j <= 1000; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (gcd(i, j) == 1) f[i][j]++;
        }
    while (T--) {
        scanf("%d%d", &a, &b);
        printf("%d\n", f[a][b]);
    }
    return 0;
}