#include "bits/stdc++.h"
using namespace std;
const int N = 1005;
const int inf = 1e9+7;

int dp[N][N];

int gcd(int a,int b){
    int r = a%b;
    while(r){
        a = b  ,b= r;
        r = a%b;
    }
    return b;
}

int main()
{
    dp[1][1] = 1;
    for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++){
        dp[i][j] = max( dp[i-1][j] , dp[i][j-1] );
        if(gcd(i,j)==1) dp[i][j]++;
    }
    int t;  scanf("%d",&t);
    while(t--){
        int a,b;  scanf("%d%d",&a,&b);
        printf("%d\n",dp[a][b]);
    }
}