#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000;

int b[MAXN+4][MAXN+4];

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

int main() {
    for(int i = 1; i <= MAXN; ++i) {
        for(int j = 1; j <= MAXN; ++j) {
            b[i][j] = max(b[i-1][j], b[i][j-1]);
            if(gcd(i, j) == 1) ++b[i][j];
        }
    }
    int T; scanf("%d", &T);
    while(T--) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", b[x][y]);
    }
    return 0;
}