% Автор: Сергей Копелиович
% Источник: СПБ АУ, пары бакалавров, весенний семестр 2014-2015

\begin{problem}{Длинный наибольший общий делитель}
{agcd.in}{agcd.out}
{1 секунда}{256 мегабайт}{}

Даны два целых положительных числа. Найти их наибольший общий делитель.

\InputFile

Мультитест.
Каждый тест задаётся двумя строками. Суммарная длина чисел до $50\,000$.

\OutputFile

Для каждого теста выведите одну строку -- наибольший общий делитель.

\Examples

\begin{example}
\exmp{
10
15
1000000000000000000
1152921504606846976
17
100
}{
5
262144
1
}%
\end{example}

\Hint

Решение за $\O(\frac{n^2}{k^2})$ зайдёт по времени. Система счисления равна $10^k$.

\end{problem}
