#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
typedef pair<int,int> pii;
int f[1010][1010];
int gcd(int a,int b) {
    return !b?a:gcd(b,a%b);
}
int main() {
    rep(i,1,1000) rep(j,1,1000) if(i+j>=2) {
        int c=0;
        if(i>1) c=f[i-1][j];
        if(j>1) c=max(c,f[i][j-1]);
        f[i][j]=c+(gcd(i,j)==1);
    }
    int T=read();
    while(T--) {
        int a=read(),b=read();
        printf("%d\n",f[a][b]);
    }
    return 0;
}