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

const int N = 4010;
const int M = 100100;
#define inf 0x3f3f3f3f
typedef long long ll;



int f[1001][1001];


int main()
{
    for (int i = 1; i <= 1000; ++i) {
        for (int j = 1; j <= 1000; ++j) {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if (__gcd(i, j) == 1) {
                f[i][j]++;
            }
        }
    }
    int _;
    for (scanf("%d", &_); _; _ --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        cout << f[a][b] << '\n';
    }
}