#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;

int T,x,y;
int f[1010][1010];

int read()
{
    static int x;
    static char ch;
    x = 0;
    for (ch = getchar();ch>'9' || ch<'0';ch=getchar());
    for (;ch <='9' && ch >='0';ch=getchar()) x = x * 10 + ch - '0';
    return x;
} 
int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y,x%y);
}
int find(int x,int y)
{
    if (f[x][y]!=0) return f[x][y];
    if (x == 1 || y == 1) return f[x][y] = max(x,y);
    return f[x][y] = max(find(x-1,y),find(x,y-1)) + (gcd(x,y)==1);
}
int main()
{
    T = read();
    find(1000,1000);
    for (int i = 1;i<=T;++i)
    {
        x = read(); y = read();
        printf("%d\n",find(x,y)); 
    }
    return 0;    
}