#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int t, dp[1001][1001] = { 0 };

int gcd(int m, int n)
{
    while (m > 0)
    {
        int c = n % m;
        n = m;
        m = c;
    }
    return n;
}

int main()
{
    dp[1][1] = 1;
    for (int i = 1, j = 2; j <= 1000; j++)
    {
        for (int k = 0; j - k > 0 && i + k <= 1000; k++)
        {
            int x = i + k, y = j - k;
            dp[x][y] = max(dp[x - 1][y], dp[x][y - 1]);
            if (gcd(x, y) == 1)
                dp[x][y]++;
        }
    }
    for (int i = 2, j = 1000; i <= 1000; i++)
    {
        for (int k = 0; j - k > 0 && i + k <= 1000; k++)
        {
            int x = i + k, y = j - k;
            dp[x][y] = max(dp[x - 1][y], dp[x][y - 1]);
            if (gcd(x, y) == 1)
                dp[x][y]++;
        }
    }
    scanf("%d", &t);
    while (t--)
    {
        int x, y; scanf("%d%d", &x, &y);
        printf("%d\n", dp[x][y]);
    }
    return 0;
}