#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int dp[1000][1000];

int main (){
   int T;
   cin>>T;
   dp[1][1]=1;
   for(int i=1;i<=1000;i++){
       for(int j=i;j<=1000;j++){
           dp[i][j]=max(dp[i-1][j],dp[i][j-1])+(gcd(i,j)==1);
           dp[j][i]=dp[i][j];
       }
   }
   while(T--){
       int a,b;
       scanf("%d%d",&a,&b);
       if(a>b) swap(a,b);
       printf ("%d\n",dp[a][b]);


   }

}