#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;

int cache[1001][1001];


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

int main(void) {
    memset(cache, 0, sizeof(cache));

    for (int j = 1; j <= 1000; ++j) {
        cache[j][1] = j;
        // cache[1][j] = j;
    }

    for (int i = 2; i <= 1000; ++i) {
        for (int j = 2; j <= i; ++j) {
            int t = max(cache[i-1][j], cache[i][j-1]);
            if (gcd(i, j) == 1) ++t;
            cache[i][j] = t;
        }
    }

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    int a, b;
    stringstream S;
    for (int i = 1; i <= T; ++i) {
        cin >> a >> b;
        if (a < b) { int t = a; a = b; b = t; }
        S << cache[a][b] << endl;
    }
    cout << S.str();
    return 0;
}