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