#include<cstdio>
#define M 2000000
char p[M];
int t,a,b,i=-1,r,k;
int A(char c)
{
int s=0;
for(i++;p[i]!=c;i++)
s=s*10+p[i]-48;
return s;
}
void S(int b)
{
char e[100];
int j;
if(b<10)
p[k++]=b;
else if(b<100)
p[k++]=(b/10)%10,p[k++]=b%10;
else if(b<1000)
p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
else if(b<10000)
p[k++]=(b/1000)%10,p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
else if(b<100000)
p[k++]=(b/10000)%10,p[k++]=(b/1000)%10,p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
else if(b<1000000)
p[k++]=(b/100000)%10,p[k++]=(b/10000)%10,p[k++]=(b/1000)%10,p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
else if(b<10000000)
p[k++]=(b/1000000)%10,p[k++]=(b/100000)%10,p[k++]=(b/10000)%10,p[k++]=(b/1000)%10,p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
else if(b<100000000)
p[k++]=(b/10000000)%10,p[k++]=(b/1000000)%10,p[k++]=(b/100000)%10,p[k++]=(b/10000)%10,p[k++]=(b/1000)%10,p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
else if(b<1000000000)
p[k++]=(b/100000000)%10,p[k++]=(b/10000000)%10,p[k++]=(b/1000000)%10,p[k++]=(b/100000)%10,p[k++]=(b/10000)%10,p[k++]=(b/1000)%10,p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
else
p[k++]=(b/1000000000)%10,p[k++]=(b/100000000)%10,p[k++]=(b/10000000)%10,p[k++]=(b/1000000)%10,p[k++]=(b/10000)%10,p[k++]=(b/1000)%10,p[k++]=(b/100)%10,p[k++]=(b/10)%10,p[k++]=b%10;
/*for(j=0;b;b/=10,j++)
e[j]=b%10+48;
for(j--;j>=0;j--)
p[k++]=e[j];*/
p[k++]='\n';
}
int main()
{
freopen("euclid2.in","r",stdin),freopen("euclid2.out","w",stdout),fread(p,1,M,stdin),t=A('\n');
while(t--)
{
for(a=A(' '),b=A('\n');r=a%b;a=b,b=r);
S(b);
}
fwrite(p,1,k,stdout);
}