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

int dp[1003][1003] , gcd[1003][1003] , T;

int main(){
    for(int i = 1 ; i <= 1000 ; ++i) gcd[i][0] = gcd[0][i] = i;
    for(int i = 1 ; i <= 1000 ; ++i)
        for(int j = 1 ; j <= 1000 ; ++j){
            if(i > j) gcd[i][j] = gcd[j][i];
            else gcd[i][j] = gcd[i][j - i];
            dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]) + (gcd[i][j] == 1);
        }
    ios::sync_with_stdio(0);
    for(cin >> T ; T ; --T){
        int x , y; cin >> x >> y; cout << dp[x][y] << '\n';
    }
    return 0;
}