#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
    x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

int dp[1001][1001];
inline void init(){
    int i,j;
    for (i = 1; i <= 1000; ++i) for (j = 1; j <= 1000; ++j){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        if (__gcd(i,j)==1) dp[i][j]++;
    }
}
int main(){
    int T,a,b;
    init(); 
    read(T);
    while (T--){
        read(a),read(b),write(dp[a][b]),putchar('\n');
    }
    return 0;
}