#include<bits/stdc++.h>
using namespace std;
template<class T> void gi(T& ret){
    ret=0; char c=getchar(); int f=1;
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar())
        ret=ret*10+(c-'0');
    ret*=f;
}
template<class T>void pi(T x){
    if(x>9) pi(x/10);
    putchar(x%10+'0');
}
int f[1005][1005],g[1005][1005];
int main(){
    int T; gi(T); 
    for(int x=1;x<=1000;++x)
        for(int y=1;y<=x;++y){
            if(x%y==0) g[x][y]=y;
            else g[x][y]=g[y][x%y];
            if(x==1) f[x][y]=1;
            else if(y==1) f[x][y]=f[x-1][y]+1;
            else if(x==y) f[x][y]=f[x][y-1]+(g[x][y]==1);
            else f[x][y]=max(f[x-1][y],f[x][y-1])+(g[x][y]==1);
//            printf("[%d %d %d %d]",x,y,g[x][y],f[x][y]);
        }
    while(T--){
        int x,y; gi(x); gi(y);
        if(x<y) swap(x,y);
        pi(f[x][y]); putchar('\n');
    }
    return 0;
}