Програмчлалын үндсэн аргууд

Сөрөг биш бүхэл тоонуудын хамгийн их ерөнхий хуваагчийг (ХИЕХ) олох Евклидийн алгоритм эдгээр тооны дараах чанарт үндэслэнэ: m ба n нь хоёулаа зэрэг тэгтэй тэнцүү биш сөрөг биш бүхэл тоонууд бөгөөд m ≥ n байг. Хэрэв n=0 бол ХИЕХ(m, n)=m, харин n ≠ 0 бол m, n ба r тоонуудын хувьд дараах тэнцэтгэл биелнэ: ХИЕХ(m, n)= ХИЕХ (n, r). Энд r: m тоог n-д хуваасны үлдэгдэл. Жишээ нь ХИЕХ(15, 6)= ХИЕХ(6, 3)= ХИЕХ(3, 0)=3. n, m натурал тоонууд өгөгдөв. Евклидын алгоритмыг ашиглан m, n тоонуудын ХИЕХ-ийг ол.

Input

m, n натурал тоонууд өгөгдөнө (n<2000000000, m<2000000000)

Output

ХИЕХ(m, n)-г хэвлэнэ

Example

Input:
56 108

Output:
4