#include<stdio.h>
#include<iostream>
#include<algorithm>
#define MAXN 1005
#define mod 10009
using namespace std;
int dp[MAXN][MAXN];
int main()
{
    for(int i=1;i<1001;i++){
        dp[1][i]=i;
        dp[i][1]=i;
    }
    for(int i=2;i<=1000;i++){
        for(int j=i;j<=1000;j++){
            dp[i][j]+=max(dp[i-1][j],dp[i][j-1]);
            if(__gcd(i,j)==1)
                dp[i][j]++;
            dp[j][i]=dp[i][j];
        }
    }
    int n,a,b;
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&a,&b);
        printf("%d\n",dp[a][b]);
    }
    return 0;
}