#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int a[1005][1005];
int gcd(int a,int b)
{
   return a%b==0?b:gcd(b,a%b);
}
int main(){
    int t,x,y;
    scanf("%d",&t);
    for(int i=1;i<=1000;i++) {
        for(int j=1;j<=1000;j++) {
            if(a[i][j]==1) continue;
            if(gcd(i,j)==1) a[i][j]=1,a[j][i]=1;
        }
    }
    for(int i=1;i<=1000;i++) {
        dp[i][1]=i;
        dp[1][i]=i;
    }
    for(int i=2;i<=1000;i++) {
        for(int j=2;j<=1000;j++) {
            if(dp[i][j]!=0) continue;
            dp[i][j]=max(dp[max(i-1,1)][j],dp[i][max(j-1,1)])+a[i][j];
            dp[j][i]=dp[i][j];
        }
    }
    while(t--) {
        scanf("%d %d",&x,&y);
        printf("%d\n",dp[x][y]);
    }
return 0;
}