시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 6 5 100.000%

문제

Vilibald has decided to cut a right-angled checked page of size n×m cells into squares. First of all he cut off the largest possible square using a straight cut. Then he took away the square and repeated the action with the remaining rectangle. In this way (all the time cutting off the largest possible square) Vilibald continued cutting until the remaining rectangle was a square.

Your task is to write a program that for n and m values (n<10000, m<10000) given in the input data computes, how many squares Vilibalds obtained by cutting the rectangle in the way described above.

예제 입력 1

3 7

예제 출력 1

5

예제 입력 2

9999 9999

예제 출력 2

1