#include <bits/stdc++.h>

using namespace std;

int test, a, b, f[1001][1001], g[1001][1001];

int gcd(int x, int y) { return g[x][y] ? g[x][y] :
    g[x][y] = y ? gcd(y, x % y) : x; }

int main() {
  for (int i = 1; i <= 1000; ++i)
    for (int j = 1; j <= 1000; ++j)
      f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (gcd(i, j) == 1);
  scanf("%d", &test);
  while (test--) {
    scanf("%d%d", &a, &b);
    printf("%d\n", f[a][b]);
  }
  return 0;
}