#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    int dp[1001][1001] = {};
    for (int i = 1; i <= 1000; ++i)
        for (int j = 1; j <= 1000; ++j)
            dp[i][j] = (std::__gcd(i, j) == 1) + std::max(dp[i - 1][j], dp[i][j - 1]);
    while (t--) {
        int a, b;
        std::cin >> a >> b;
        std::cout << dp[a][b] << "\n";
    }
    return 0;
}