#include <bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;
typedef double db;

bool vis[1005][1005];
int f[1005][1005];

int dp(int n,int m) {
  if (n==1&&m==1) return 1;
  if (vis[n][m]) return f[n][m];
  vis[n][m]=1;
  if (n>1) f[n][m]=max(f[n][m],dp(n-1,m));
  if (m>1) f[n][m]=max(f[n][m],dp(n,m-1));
  f[n][m]+=(__gcd(n,m)==1);
  return f[n][m];
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
      int n,m;
      scanf("%d%d",&n,&m);
      printf("%d\n",dp(n,m));
  }
  return 0;
}