#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#include <cmath>
#include <map>
using namespace std;

const int maxn = 1010;

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

int T;

int f[maxn][maxn] = {0};

void init() {
    f[1][1] = 1;
    for (int a = 1; a <= 1000; ++a) {
        for (int b = 1; b <= 1000; ++b) {
            if (a == 1 && b == 1) continue;
            if (a != 1) f[a][b] = max(f[a][b], f[a - 1][b]);
            if (b != 1) f[a][b] = max(f[a][b], f[a][b - 1]);
            if (gcd(a, b) == 1) f[a][b]++;
        }
    }
}

int a, b;

int main() 
{
    ios::sync_with_stdio(0);
    init();
    cin >> T;
    while (T--) {
        cin >> a >> b;
        cout << f[a][b] << endl;
    }
    return 0;
}