#include <stdio.h>
#include <stdlib.h>

int cmmdc(int a, int b) {
    if(a==0)
        return b;
    else
        if(b==0)
            return a;
    if(a>b)
    {
        cmmdc(a-b,b);
    }
    else
        cmmdc(a, b-a);
}


int main()
{
    int n,a,b,i,d;
    FILE* f;
    FILE* g;
    f = fopen("euclid2.in","r");
    g = fopen("euclid2.out","w");
    fscanf(f,"%d", &n);
    printf("%d",n);
    for(i=0;i<n;i++) {
        fscanf(f,"%d %d", &a, &b);
        d=cmmdc(a,b);
        fprintf(g, "%d \n", d);
    }
    fclose(f);
    fclose(g);
    return 0;
}