뛰는 기물

장기에는 마(馬)와 상(象)이라는 두 가지 뛰는 기물이 있다. 다른 기물들과 다른 이 기물들의 공통점은 가로와 세로로 동시에 움직인다는 것이다. 따라서 이동 경로를 직선으로 그리면 항상 장기판의 가로 선과 세로 선을 빗겨가게 된다. 마(馬)는 가로 혹은 세로 방향으로 한 칸, 다른 방향으로 두 칸 이동하고, 상(象)은 가로 혹은 세로 방향으로 두 칸, 다른 방향으로 세 칸 이동한다.

마(馬)와 상(象)의 이동 경로 예시. 왼쪽이 마(馬), 오른쪽이 상(象)이다.

뛰는 기물의 존재 여부는 장기의 후반 흐름을 좌우할 만큼 중요하다. 오로지 장기가 재밌어서 이런 중책을 천 번도 넘게 맡긴 키파는, 마(馬)와 상(象)이 뛰는 기물로서 자부심을 가질 수 있도록 특별한 이름을 붙여 주기로 했다. 그 이름은 기물이 각 방향으로 움직이는 칸 수를 앞에 붙여서 $(n, m)$-기물과 같이 정했다. 예를 들어 마(馬)는 이제 $(1, 2)$-기물 혹은 $(2, 1)$-기물, 상(象)은 $(2, 3)$-기물 혹은 $(3, 2)$-기물이다.

이런 이름을 붙이자 키파는 다른 $(N, M)$-기물의 특성 역시 생각해 보기로 했다. 이를 위해 장기판은 조금 답답했기 때문에 무한히 넓은 좌표평면을 생각하기로 했다. 곧 키파는 마(馬)와 상(象)과는 다르게 $N$, $M$에 따라 특정 지점에서 다른 지점으로 항상 갈 수 있는 것은 아니라는 것을 깨달았다. 예를 들어 $(2, 4)$-기물은 좌표평면의 $(0, 0)$ 위치에서 $(3, 3)$ 위치로 갈 수 없다.

키파는 $(N, M)$-기물을 기특히 여겨 선물을 주려고 한다. 그러나 기물이 너무 멀리 뛰어가 버려서 키파는 기물의 위치를 정확히 알 수 없었고, 대신 격자점 위에 선물을 두고 돌아가기로 했다. 기물이 선물이 놓인 격자점을 방문할 수 없게 되는 것이 걱정된 키파는 선물을 많이 가져와서 여러 곳의 격자점에 하나씩 놓기로 했다. 기물이 어떤 위치에 있더라도 선물이 놓인 격자점에 방문할 수 있도록 하기 위해, 키파가 준비해야 하는 선물의 최소 개수를 구해 보자.

첫째 줄에 음이 아닌 정수 $N$과 $M$이 공백을 사이에 두고 주어진다. $N$과 $M$은 모두 $10^{9}$보다 작거나 같으며, $N$과 $M$이 모두 $0$인 입력은 주어지지 않는다.

첫째 줄에 키파가 준비해야 하는 선물의 최소 개수를 출력한다.

첫 번째 예제의 경우 가로 축과 세로 축에서 모두 홀수 점들과 짝수 점들이 나누어져 있기 때문에 답은 최소 $2 \times 2 = 4$이다. 선물을 $4$개만 준비해도 된다는 사실을 증명할 수 있다.

두 번째 예제의 경우, 예를 들어 $(0, 0) \rightarrow (1, 2) \rightarrow (3, 1) \rightarrow (1, 0)$과 같은 방식으로 한 칸씩 이동할 수 있기 때문에 어떤 위치에든 선물을 하나만 놓아도 기물이 선물을 가져갈 수 있다.

세 번째 예제의 경우, 두 번째 예제와 마찬가지로 기물이 한 칸씩 이동할 수 있는 방법이 있다. 이 경우는 기물이 한 칸을 이동하는 데 최소 다섯 번의 이동을 필요로 한다.