{\rtf1\ansi\ansicpg1252\cocoartf2576
\cocoatextscaling0\cocoaplatform0{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
{\colortbl;\red255\green255\blue255;}
{\*\expandedcolortbl;;}
\margl1440\margr1440\vieww11520\viewh8400\viewkind0
\pard\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\pardirnatural\partightenfactor0

\f0\fs24 \cf0 #include <stdio.h>\
#include <iostream>\
\
using namespace std;\
\
int f(int a, int b)\{\
	if (b == 0)\
		return a;\
	\
    return f(b, a%b);\
\}\
\
int main() \{\
    \
    freopen("euclid2.in", "r", "stdin");\
    freopen("euclid2.out", "w", "stdout");\
    \
    int t, a, b;\
    cin >> t;\
    \
    for (int i=0; i<t; i++)\{\
        cin >> a >> b;\
        cout << f(a, b) << "\\n";\
    \}\
    \
    return 0;\
\}\
}