#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
const int mod = 1e9+7;
ll dp[1005][1005];
int main() {

  for(int i=1;i<=1000;i++){
    for(int j=1;j<=1000;j++){
      if(__gcd(i,j)==1) dp[i][j]++;
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
      dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
    }
  }
  int t;
  scanf("%d",&t);
  while(t--){
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%lld\n",dp[x][y]);
  }
  return 0;
}