#include <iostream>
#include <cstdio>
using namespace std;

int _gcd(int a, int b){
    if(b == 0)  return a;
    return _gcd(b, a % b);
}
int dp[1005][1005];


int main(){
    for(int i = 1; i <= 1000; ++i){
        for(int j = 1; j <= 1000; ++j){
            dp[i][j] = _gcd(i, j);
            if(dp[i][j] > 1) dp[i][j] = 0;
        }
    }
    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]) + dp[i][j];
        }
    }
    int T;
    scanf("%d", &T);
    while (T --){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dp[a][b]);
    }
    return 0;
}