시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB84443854.286%

문제

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