#include <stdio.h>
#include <time.h>
 
int cmmdc(int a, int b);

int main()
{
    int a, b;
    int i, t;
    clock_t begin, end;
    double time_spent;
    int x=1;
    int j,k;
    begin = clock();
    FILE* fin = fopen("euclid2.in","r");
    FILE* fout = fopen("euclid2.out","w");
    fscanf(fin, "%d", &t);
    for(i=0; i<t; i++)
    {
    	fscanf(fin, "%d", &a);
    	fscanf(fin, "%d", &b);
    	fprintf(fout, "%d\n", cmmdc2(a,b));
	}
    fclose(fin);
    fclose(fout);
    end = clock();
    time_spent = (double)(end - begin);
    printf("%f", time_spent / CLOCKS_PER_SEC);
    return 0;
}

int cmmdc(int a, int b)
{
	if ((a==1) || (a==b)) return a;
	if (b==1) return b;
	if (a>b) return cmmdc(a-b,b);
	return cmmdc(a,b-a);
}

int cmmdc2(int a, int b)
{
	if((a==0) || (a==b)) return b;
	if(b==0) return a; 
	if (a>b) return cmmdc2(a%b, b);
	return cmmdc2(a, b%a);
}