#include <bits/stdc++.h>

using namespace std;

namespace jumpmelon
{
    int gcd(int a, int b)
    {
        while (a)
        {
            int t = b % a;
            b = a;
            a = t;
        }
        return b;
    }

    const int MAXA = 1000;
    int F[MAXA + 1][MAXA + 1];

    void work()
    {
        for (int i = 1; i <= MAXA; i++)
            for (int j = 1; j <= MAXA; j++)
                F[i][j] = max(F[i - 1][j], F[i][j - 1]) + (gcd(i, j) == 1 ? 1 : 0);
        int kase;
        scanf("%d", &kase);
        while (kase--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", F[x][y]);
        }
    }
}

int main()
{
    jumpmelon::work();
    return 0;
}