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

typedef long long ll;



int dp[1010][1010];
int main() {


    for(int i = 1; i <= 1000; i++) {
        for(int j = 1; j <= 1000; j++) {
            int x = (__gcd(i, j) == 1);
            dp[i][j] = max(dp[i - 1][j] + x, dp[i][j - 1] + x);
        }
    }
    int t;
    scanf("%d", &t);
    while(t--) {

        int a, b;
        scanf("%d%d", &a, &b);

        printf("%d\n", dp[a][b]);

    }
}