#include<bits/stdc++.h>
using namespace std;

const int maxn=1005;
int dp[maxn][maxn];

int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

int main(){
    for(int i=1;i<=1000;i++)for(int j=1;j<=1000;j++)
        dp[i][j]=max(i>1?dp[i-1][j]:0,j>1?dp[i][j-1]:0)+(gcd(i,j)==1);
    int T;
    scanf("%d",&T);
    while(T--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",dp[x][y]);
    }
    return 0;
}