#include<bits/stdc++.h>
using namespace std;
const int maxn=21111;
int dp[1005][1005];

int main(){
    for (int i=1;i<=1000;i++)
    for (int j=1;j<=1000;j++){
        int res=0;
        if (i>1) res=max(res,dp[i-1][j]);
        if (j>1) res=max(res,dp[i][j-1]);
        dp[i][j]=res+(__gcd(i,j)==1);
    }
    int _; cin >> _;
    while (_--){
        int x,y;scanf("%d%d",&x,&y);
        printf("%d\n",dp[x][y]);
    }
    return 0;
}