#include <iostream>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <string>
#include <vector>
#include <map>
#include <cassert>

using namespace std;
int dp[1100][1100] = { 0 };
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}
void prework() {
    dp[1][1] = 1;
    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]);
            if (gcd(i, j) == 1) dp[i][j] ++;
        }
    }
}
void work() { 
    int a, b;
    cin >> a >> b;
    cout << dp[a][b] << endl;
}

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); // close sync between cout and printf
    int T;
    cin >> T;
    prework();
    for (int ii=1; ii<=T; ++ii) {
        work();
    }
    return 0;
}