/*********************************************************************
    > File Name: 3.cpp
    > Author: yuki
 *********************************************************************/

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

typedef long long ll;

int dp[1005][1005];

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

int main()
{
    int t;
    scanf("%d", &t);
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=1000; i++)
        for(int j=1; j<=1000; j++)
        {
            dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
            if(gcd(i, j) == 1)
                dp[i][j]++;
        }
    while(t--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dp[a][b]);
    }
    return 0;
}