#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>

using namespace std;

int f[1010][1010];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int dp(int a, int b)
{
    if (!a || !b) return f[a][b] = 0;
    if (a == 1 && b == 1) return f[a][b] = 1;
    if (f[a][b] > -1) return f[a][b];
    int v = gcd(a, b) == 1 ? 1 : 0;
    f[a][b] = max(dp(a - 1, b), dp(a, b - 1)) + v;
    
    return f[a][b];
}

int main()
{
    memset(f, -1, sizeof f);
    int T; scanf("%d", &T);
    while (T -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dp(a, b));
    }
    
    return 0;
}