По данным натуральным числам n и m найдите их наибольший общий делитель.
Указание. Верно следующее тождество: НОД(n,m)=НОД(n mod m,m). Таким образом, можно от одной пары (n,m) перейти к поиску НОД новой пары чисел. Далее от той пары можно снова перейти к новой паре. И так далее. Этот алгоритм называется алгоритмом Евклида.
Входные данные
Программа получает на вход 2 натуральных числа n и m. Числа n и m не превосходят 109.
Замечание. Для работы с такими числами используйте тип данных longint.
Выходные данные
Программа должна вывести наибольший общий делитель двух данных чисел.
Пример ввода
6 4
Пример вывода
2