#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh 
using namespace std;

int f[1005][1005];
int gcd(int x,int y){
    return y?gcd(y,x%y):x;
}
void solve(){
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%d\n",f[x][y]);
}
int main(){
    For(i,1,1000) For(j,1,1000)
        f[i][j]=max(f[i][j-1],f[i-1][j])+(gcd(i,j)==1);
    int T;
    scanf("%d",&T);
    while (T--) solve();
}