3458 - 3분만에 풀 수 있는 문제

• Submit
• Status
• Discuss
• Summary

Description

당신에게 정사각형 모양의 타일을 주문하는 일이 주어졌다. 그런데 실수로 직사각형 형태로 타일을 주문해버렸다는 것을 뒤늦게 깨달았다! 3분 뒤에 업체랑 미팅이 잡혀있는데...이대로 가다간 큰일이 날 것이다.

여기서 포기할 순 없지! 당신은 타일들을 적절히 조합해서 정사각형 모양으로 만들었다.

음 이제 좀 정사각형같이 생겼네.

하지만 정사각형 타일이 굉장히 많이 필요하다. 타일을 요구할 때마다 저렇게 복잡한 모양의 타일을 일일히 배치하는 것은 불필요한 행위이다.

이에 당신은 타일을 좀 더 적게 사용해서 정사각형을 만들 수 있는지 확인해보았다.

만족스럽다. 길이가 2, 3인 타일을 이용해서는 최소 6개를 이용해야지만 정사각형 모양의 타일을 만들 수가 있다.

조금 마음의 여유가 생긴 당신은 실수로 주문한 타일의 가로세로 길이가 주어졌을 때, 정사각형 타일로 만드는데 필요한 타일의 개수의 최소값을 구하는 프로그램을 만들고 싶어졌다.

이제 미팅까지 3분정도 남았...아니다, 이 문제를 읽느라 1분을 써버린 당신! 당신은 과연 2분만에 프로그램을 작성할 수 있을 것인가....

 

 

Input

입력은 여러 테스트케이스로 주어진다.

각 테스트케이스마다 타일의 가로세로 길이를 나타내는 2개의 정수 H,W가 주어진다. (1 ≤ H, W ≤ 1,000,000)

H,W가 0 0으로 주어지면 입력을 종료한다.

Output

각 테스트케이스마다 한줄에 하나씩 정답을 출력한다.

Sample Input

2 3 
1 2 
2 4
0 0

Sample Output

6
2
2

Source

Regionals 2009, Africa/Middle East - Africa and Arab