#include <bits/stdc++.h>
using namespace std;

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    static int dp[1001][1001];
    for (int i = 1; i <= 1000; ++i) {
        for (int j = 1; j <= 1000; ++j) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + (gcd(i, j) == 1);
        }
    }
    int test;
    cin >> test;
    while (test--) {
        int a, b;
        cin >> a >> b;
        cout << dp[a][b] << '\n';
    }
}