#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1001;

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

int f[N][N];

void init()
{
    for (int i = 1; i < N; ++i)
        f[1][i] = f[i][1] = i;
    for (int i = 2; i < N; ++i)
        for (int j = 2; j < N; ++j)
            f[i][j] = (gcd(i, j) == 1) + max(f[i-1][j], f[i][j-1]);
}

int main()
{
    init();
    int T, x, y;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &x, &y);
        printf("%d\n", f[x][y]);
    }
    return 0;
}