#include<bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 1005;
int T, f[N][N];
int main() {
    for(int i=1; i<=1000; ++i) for(int j=1; j<=1000; ++j)
        f[i][j]=max(f[i][j-1], f[i-1][j])+(__gcd(i, j)==1);
    scanf("%d", &T);
    while(T--){
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", f[x][y]);
    }
    return 0;
}