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

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

const int INF = 0x3f3f3f3f;

const int N = 1111;

int dp[N][N];

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

int dfs(int a, int b) {
    if (a > b) {
        return dfs(b, a);
    }
    assert(a <= b);

    if (dp[a][b] != -1) {
        return dp[a][b];
    }

    int res = 0;
    if (gcd(a, b) == 1) {
        res++;
    }

    int aa = -INF;
    int bb = -INF;

    if (a - 1 >= 1) {
        aa = dfs(a - 1, b);
    }

    if (b - 1 >= 1) {
        bb = dfs(a, b - 1);
    }

    res += max(aa, bb);
    return dp[a][b] = res;
}

int main() {
    memset(dp, -1, sizeof(dp));

    dp[1][1] = 1;
    for (int i = 1; i <= 1000; i++) {
        for (int j = i; j <= 1000; j++) {
            dfs(i, j);
        }
    }

    int T;
    input(T);

    int a, b;
    while (T--) {
        scanf("%d%d", &a, &b);
        printf("%d\n", dfs(a, b));
    }
    
    return 0;
}