/***************************************************************
    File name: a.cpp
    Author: huhao
    Create time: Sun 19 Jul 2020 02:02:40 PM CST
***************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
int read()
{
    int r=0,t=1,c=getchar();
    while(c<'0'||c>'9')
    {
        t=c=='-'?-1:1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        r=r*10+c-48;
        c=getchar();
    }
    return r*t;
}
const int N=1010,inf=123456789;
int n,ans;
int f[N][N];
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
#define Max(a,b) a=std::max(a,b)
int main()
{
    n=1000; f[1][1]=1;
    fr(i,1,n) fr(j,1,n)
    {
        Max(f[i+1][j],f[i][j]+(gcd(i+1,j)==1));
        Max(f[i][j+1],f[i][j]+(gcd(i,j+1)==1));
    }
    fr(T,1,read()) printf("%d\n",f[read()][read()]);
    return 0;
}