#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e3 + 70;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);

int n, m, k;

int dp[maxn][maxn];

void init(){
    for(int i=1;i<maxn;i++){
        for(int j=1;j<maxn;j++){
            dp[i][j] = (__gcd(i,j)==1) + max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

int main(){
    //freopen("in.txt", "r", stdin);
    init();
    int T; cin>>T;
    while(T--){
        scanf("%d %d",&n,&m);
        printf("%d\n",dp[n][m]);
    }
    return 0;
}