#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long int

ll read(){
    char ch=getchar();
    ll sum=0;
    bool ttt=false;
    while(!isdigit(ch)) ttt=(ch=='-'),ch=getchar();
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch-'0'),ch=getchar();
    return ttt?-sum:sum;
}

ll tst;
int a,b;
int f[1010][1010];

int gcd(int x,int y){
    if(y) return gcd(y,x%y);
    return x;
}

int main(){
    for(int i=1;i<=1000;i++){
        for(int j=i;j<=1000;j++){
            f[i][j]=max(f[i][j-1],f[i-1][j])+(gcd(i,j)==1);
        }
    }
    tst=read();
    for(int i=1;i<=tst;i++){
        a=read(),b=read();
        printf("%d\n",f[min(a,b)][max(a,b)]);
    }
    return 0;
}