#include <iostream>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
using namespace std;

int dp[1001][1001];

int main() {
  ios::sync_with_stdio(false);

  int test;
  cin >> test;

  for(int i = 1; i <= 1000; ++i)
    for(int j = 1; j <= 1000; ++j) {
      dp[i][j] = max(i > 1 ? dp[i - 1][j] : 0, j > 1 ? dp[i][j - 1] : 0) + (__gcd(i, j) == 1);
    }
  while(test--) {
    int a, b;
    cin >> a >> b;
    cout << dp[a][b] << '\n';
  }
  return 0;
}