#include <stdio.h>
#include <algorithm>

using namespace std;

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