h2. Cerinta

Dandu-se doua numere naturale $a$ si $b$ sa se calculeze cel mai mare divizor comun al lor.

Dandu-se $T$ perechi de numere naturale {$(a, b)$}, sa se calculeze cel mai mare divizor comun al numerelor din fiecare pereche in parte.

h2. Date de intrare

Fisierul de intrare $euclid2.in$ contine pe prima linie doua numere naturale $a$ si $b$.

Fisierul de intrare $euclid2.in$ contine pe prima linie numarul $T$ de perechi. Urmatoarele $T$ linii contin cate doua numere naturale $a$ si $b$.

h2. Date de iesire

In fisierul de iesire $euclid2.out$ se va afisa o singura linie ce contine rezultatul cerut.

In fisierul de iesire $euclid2.out$ se vor scrie $T$ linii. A $i$-a linie din acest fisier contine cel mai mare divizor comun al numerelor din perechea de pe linia $i+1$ din fisierul de intrare.

h2. Restrictii

* $2 ≤ a, b ≤ 2 * 10^9^$

* $T ≤ 100 000$
* Pentru fiecare pereche, $2 ≤ a, b ≤ 2 * 10^9^$

h2. Exemplu
table(example). |_. euclid2.in |_. euclid2.out |

|12 42|6|

|3
12 42
21 7
9 10
|6
7
1|

h2. Indicatii de rezolvare