题目描述

欧几里得算法又称辗转相除法，定义是：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

因此只要对除数和余数反复做除法运算，当余数为0时，当前算式的除数就是最初两个数的最大公约数。

例如：48除以18，余数是12；

接下来，18除以12，余数为6； 接下来，12除以6，余数为0； 所以，6就是48和18的最大公约数。

输入

第一行输入一个正整数a；第二行输入一个正整数b。(a<$10^7$,b<$10^7$)

输出

使用欧几里得算法计算a和b的最大公约数，并输出结果。

48 
18

6