#include<bits/stdc++.h>
using namespace std;
int dp[1000+9][1000+9];
void dfs(int a,int b){
    if( dp[a][b] != -1 ) return;
    int res = 0;
    if(__gcd(a,b) == 1) res = 1;
    if(a>1){
        dfs(a-1,b);
        dp[a][b] = max(dp[a][b],res + dp[a-1][b]);
    }
    if( b > 1){
        dfs(a,b-1);
        dp[a][b] = max(dp[a][b],res + dp[a][b-1]);
    }
}
int main(){
    memset(dp,-1,sizeof(dp));
    dp[1][1] = 1;
    int T; scanf("%d",&T);
    while(T--){
        int a,b; scanf("%d %d",&a,&b);
        dfs(a,b);
        printf("%d\n",dp[a][b]);
    }
    return 0;
}