/*
 * =template=.cpp
 * Copyright (C) 2017 hzw <hzw@huzhenweideMacBook.local>
 *
 * Distributed under terms of the MIT license.
 */

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cassert>
#define FR first
#define SC second
#define MP make_pair
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define ws wss
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
template<class T> void upmax(T &a,T b) { if (a<b) a=b;}
template<class T> void upmin(T &a,T b) { if (a>b) a=b;}
void read(int &x)
{
    char ch;int fu=1;
    while ((ch=getchar())<=32);
    x=0;
    if (ch=='-') fu=-1;else x=ch-48;
    while ((ch=getchar())>32) x=x*10+ch-48;
    x*=fu;
}
const double pi=acos(-1);
void upmax(int &a,int b) { if (a<b) a=b;}
void upmin(int &a,int b) { if (a>b) a=b;}
//-----------------------
int f[1010][1010];
int gcd(int a, int b){return b==0?a:gcd(b,a%b);}
int main()
{
    int cas;
    scanf("%d", &cas);
    for (int i=1;i<=1000;i++)
        for (int j=1;j<=1000;j++)
        {
            int t=0;
            if (i>1) t=max(t,f[i-1][j]);
            if (j>1) t=max(t,f[i][j-1]);
            if (gcd(i,j)==1)
                t++;
            f[i][j]=t;
        }
    while (cas--)
    {
        int n,m;
        scanf("%d%d", &n,&m);
        printf("%d\n", f[n][m]);
    }
    return 0;
}