#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) {}
#define eprintf(...) do {} while(0)
#endif

template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename T>
ostream& operator << (ostream& out, const vector<T> &v) {
    int n = v.size();
    out << "{";
    for(int i = 0; i < n; ++i) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "}";
}
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &v) {
    return out << "(" << v.first << ", " << v.second << ")";
}

typedef long long LL;
typedef pair<int, int> pii;

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

int f[1005][1005];

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
#endif
    memset(f, 0, sizeof(f));
    int n = 1000;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            f[i][j] += (gcd(i, j) == 1);
        }
    int T; cin >> T;
    while(T--) {
        int x, y; cin >> x >> y;
        cout << f[x][y] << '\n';
    }
    return 0;
}