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