#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            dp[i][j]=(__gcd(i,j)==1?1:0)+max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int t;cin>>t;
    while(t--){
        int a,b;cin>>a>>b;
        cout<<dp[a][b]<<"\n";
    }
}