#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

template<class Type>
inline void R(Type &x) {
    int c = getchar();
    bool neg = 0;
    for (; c < 48 || c > 57; c = getchar())if (c == '-')neg = true;
    for (x = 0; c > 47 && c < 58; x = (Type) 10 * x + c - 48, c = getchar());
    if (neg)x = -x;
}

int gcd(int m, int n) {
    if (n == 0)
        return m;
    else
        return gcd(n, m % n);
}

int f[1001][1001];

int main() {
    for (int i = 1; i <= 1000; ++i)
        for (int j = i; j <= 1000; ++j)
            f[j][i] = f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (gcd(i, j) == 1);
    int T;
    R(T);
    while (T--) {
        int a, b;
        R(a);
        R(b);
        printf("%d\n", f[a][b]);
    }
    return 0;
}