#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<"-----------------------------------"<<endl
#define LL long long
#define uint unsigned int
#define unsigned long long
#define DB double
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
using namespace std;
inline LL read(){
    LL nm=0; bool fh=1; char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return fh?nm:-nm;
}
#define mod 998244353
namespace  CALC{
    inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
    inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
    inline int mul(LL x,LL y){return x*y%mod;}
    inline void upd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
    inline void dec(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
    inline int qpow(int x,int sq){LL res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
}using namespace CALC;

#define M 500
int n,m,g[1010][1010],f[1010][1010];
int main(){
    for(int i=1;i<=1000;i++) for(int j=1;j<=1000;j++){
        if(i==1||j==1) g[i][j]=1;
        else if(i==j) g[i][j]=i;
        else if(i>j) g[i][j]=g[i-j][j];
        else g[i][j]=g[i][j-i];
        if(i==1&&j==1) f[i][j]=1;
        else{
            if(i>1) f[i][j]=f[i-1][j]+(g[i][j]==1);
            if(j>1) f[i][j]=max(f[i][j],f[i][j-1]+(g[i][j]==1));
        }
    }
    for(int Cas=read(),x,y;Cas;--Cas)
        x=read(),y=read(),printf("%d\n",f[x][y]);
    
    return 0;
}