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

const int N = 1010;
int dp[N][N];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int dfs(int x, int y)
{
    if(dp[x][y] != -1) return dp[x][y];

    if(gcd(x, y) == 1) dp[x][y] = 1;
    else dp[x][y] = 0;

    if(x > 1 && y > 1) 
        dp[x][y] += max(dfs(x - 1, y), dfs(x, y - 1));

    else if(x > 1) 
        dp[x][y] += dfs(x - 1, y);

    else if(y > 1) 
        dp[x][y] += dfs(x, y - 1);

    return dp[x][y];
}

int main()
{
    int T;
    cin >> T;
    memset(dp, -1, sizeof dp);
    while(T --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dfs(a, b));
    }
    return 0;
}