#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<cstdio>
#define ll long long
#define lson (rt<< 1)
#define rson (rt<< 1 | 1)
#define gmid ((l+r)>> 1 )
using namespace std;

const int maxn=20000050;

int dp[1050][1050];
bool gcd(int x,int y)
{
    int t=0;
    if(x==1||y==1) return true;
    if(x==y) return false;
    if(abs(x-y)==1) return true;
    while(y>0)
    {
        t=x%y;
        x=y;
        y=t;
    }
    if(x==1) return true;
      else return false;
}

int main()
{
    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][j],max(dp[i-1][j],dp[i][j-1]));
            if(gcd(i,j)) dp[i][j]++; 
        }
    int t;
    scanf("%d",&t);
    while(t--)
      {
            int n,m;
          scanf("%d %d",&n,&m);
          printf("%d\n",dp[n][m]); 
      }    
}