#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<queue>
#include<set>
#include<map>
using namespace std;

typedef long long ll;
const int N = 1006;

int f[N][N];

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

int maxx(int a, int b)
{
    return a > b ? a : b;
}

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