테트리스가 아니라 타일!

시간 제한1초메모리 제한128 MB

요약

회전할 수 없는 W x H 타일로 채울 수 있는 가장 작은 정사각형의 넓이를 구하고 필요한 타일 수를 출력한다.

난이도: 보통10점 중 4점
유형: 수학, 정수론
정답자: 아직 제출이 없습니다

문제

완전히 같은 직사각형 타일을 대량으로 샀습니다. 타일 한 장은 가로 $W$ , 세로 $H$ 크기이며, 모든 타일은 같은 방향으로만 놓아야 합니다(회전 불가). 타일 여러 장을 빈틈없이 이어 붙여 정사각형 영역을 덮으려고 합니다. 이때 정사각형 한 변의 길이는 $W$ 의 배수이면서 동시에 $H$ 의 배수여야 합니다.

만들 수 있는 가장 작은 정사각형을 채우는 데 필요한 타일의 최소 개수를 구하세요.

입력

입력은 하나 이상의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 한 줄에 두 양의 정수 $W$ 와 $H$ 가 주어지며( $0 < W, H < 10^6$ ), 각각 타일의 가로와 세로 길이를 나타냅니다. 입력의 마지막 줄에는 두 개의 $0$ 이 주어지며, 이 줄은 처리하지 않습니다.

출력

각 테스트 케이스마다 만들 수 있는 가장 작은 정사각형을 채우는 데 필요한 타일의 최소 개수를 한 줄에 하나씩 출력합니다.

예제3

예제 1
입력
```
2 3
1 2
0 0
```
예상 출력
```
6
2
```
예제 2
입력
```
5 5
0 0
```
예상 출력
```
1
```
예제 3
입력
```
6 4
0 0
```
예상 출력
```
6
```