Задача "Алгоритм Евклида"

По данным натуральным числам n и m найдите их наибольший общий делитель.

Указание. Верно следующее тождество: НОД(n,m)=НОД(n mod m,m). Таким образом, можно от одной пары (n,m) перейти к поиску НОД новой пары чисел. Далее от той пары можно снова перейти к новой паре. И так далее. Этот алгоритм называется алгоритмом Евклида.

Входные данные

Программа получает на вход 2 натуральных числа n и m. Числа n и m не превосходят 109.

Замечание. Для работы с такими числами используйте тип данных longint.

Выходные данные

Программа должна вывести наибольший общий делитель двух данных чисел.

Пример ввода

6
4

Пример вывода

2