h2. Cerinta

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

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

h2. Date de intrare

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

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

h2. Date de iesire

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.

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

h2. Restrictii

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

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

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

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

|12 42|6|

h2. Indicatii de rezolvare
O scurta prezentare a acestui subiect gasiti 'aici':http://en.wikipedia.org/wiki/Greatest_common_divisor.

Cel mai mare divizor comun dintre doua numere $a$ si $b$ se poate calcula iterativ, printr-o simpla parcurgere a tuturor numerelor de la 2 la {$minim(a, b)$}. Aceasta rezolvare se gaseste 'aici':job_detail/153457?action=view-source si obtine 30 de puncte. Pentru a imbunatati timpul de rulare putem folosi 'algoritmul lui Euclid':http://en.wikipedia.org/wiki/Euclidean_algorithm prin 'scaderi':job_detail/153459?action=view-source, ceea ce duce la obtinerea a 60 de puncte, sau prin impartiri, 'solutie':job_detail/153481?action=view-source ce obtine punctajul maxim.

Cel mai mare divizor comun dintre doua numere $a$ si $b$ se poate calcula iterativ, printr-o simpla parcurgere a tuturor numerelor de la 2 la {$minim(a, b)$}. Aceasta rezolvare se gaseste 'aici':job_detail/142976?action=view-source si obtine 40 de puncte. Pentru a imbunatati timpul de rulare putem folosi 'algoritmul lui Euclid':http://en.wikipedia.org/wiki/Euclidean_algorithm.
O solutie de 100 de puncte, pe ideea din articolul de mai sus, o gasiti 'aici':job_detail/142977?action=view-source.

h2. Probleme similare

== include(page="template/taskfooter" task_id="euclid2") ==

==SmfTopic(topic_id="2761")==

task: euclid2

public

2759