#include<bits/stdc++.h>
inline int read(){
    int x=0,w=1;
    char ch=0;
    while (ch<'0' || ch>'9'){
        ch=getchar();
        if (ch=='-') w=-1;    
    }
    while (ch<='9' && ch>='0'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*w;
}
using namespace std;
typedef long long ll;
const int N=1005;
int dp[N][N];
int main(){
    for (int i=1;i<=1000;++i)
        for (int j=1;j<=1000;++j){
            dp[i][j]=(__gcd(i,j)==1);
            int mx=0;
            if (i>1) mx=max(mx,dp[i-1][j]);
            if (j>1) mx=max(mx,dp[i][j-1]);
            dp[i][j]+=mx;
        }
    int T=read();
    while (T--){
        int x=read(),y=read();
        printf("%d\n",dp[x][y]);
    }
    return 0;
}