#include <bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define X first
#define Y second
#define lc o<<1
#define rc o<<1|1
using namespace std;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1000+10;
const int maxm = 100000+10;
const int mod = 1e9+7;
const double eps = 1e-8;
bool f[maxn][maxn];
int dp[maxn][maxn];
void init(){
    for (int i=1;i<=1000;i++) for (int j=i;j<=1000;j++){
        f[i][j]=(__gcd(i,j)==1);
    }
}
int get_dp(int a,int b){
    if (~dp[a][b]) return dp[a][b];
    int tmp=0;
    if (a>1) tmp=max(tmp,get_dp(a-1,b));
    if (b>1) tmp=max(tmp,get_dp(a,b-1));
    return dp[a][b]=tmp+f[a][b];
}
int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    mst(dp,-1);
    init();
    int T; cin>>T;
    while (T--){
        int n,m; cin>>n>>m;
        if (n>m) swap(n,m);
        cout<<get_dp(n,m)<<"\n";
    }
    return 0;
}