#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>

using namespace std;

const int N = 1000;
const int MAXN = N + 10;
int s[MAXN][MAXN];

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

void prepare()
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            s[i][j] = (gcd(i, j) == 1);
    // for (int i = 1; i <= 10; i++) {
    //     for (int j = 1; j <= 10; j++)
    //         cerr << s[i][j] << ' ';
    //     cerr << endl;
    // }
    for (int i = 2; i <= N; i++)
        s[i][1] = s[i][1] + s[i - 1][1];
    for (int i = 2; i <= N; i++)
        s[1][i] = s[1][i] + s[1][i - 1];
    for (int i = 2; i <= N; i++)
        for (int j = 2; j <= N; j++)
            s[i][j] = max(s[i - 1][j], s[i][j - 1]) + s[i][j];
}

void work()
{
    int n, m;
    cin >> n >> m;
    cout << s[n][m] << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    prepare();
    while (T--)
        work();

    return 0;
}