moner_ari   1년 전

[문제]

Mirko는 가족들을 위한 집을 지을 땅을 사고 싶어 합니다. 그래서 그는 K개의 땅을 살펴봤습니다. 이들 땅들은 직사각형 모양이며, N개의 행과 M개의 열을 가진, N x M개의 들판으로 구성된 행렬로 볼 수 있습니다.

Mirko는 집 공사가 시작되기 전에, 땅이 꾸준히 관리되고 잔디가 깎여 있어야 한다는 것을 알고 있습니다. 그래서, Mirko는 잔디 깎기 기계 하나를 샀습니다. N개 행, M개 열로 구성된 잔디를 전부 깎기 위해, Mirko는 모든 들판을 적어도 1번씩은 가봐야 합니다. 그는 4개 방향(위, 아래, 왼쪽, 오른쪽) 중 하나의 방향을 정하고 아무 들판에서 잔디 깎기를 시작할 수 있습니다. 잔디 깎기 기계는 (현재 방향으로 인접해 있는 바로 옆 들판으로) 앞으로 나아가거나 90도로 방향을 돌리는 것만이 가능합니다. 추가로, Mirko의 안전을 위해 Mirko는 그의 땅에서만 잔디 깎기 기계를 사용할 수 있으며, 들판으로 구성된 행렬 밖으로 나갈 수 없습니다.

잔디 깎기 기계를 돌리는 것이 간단하지 않기 때문에, Mirko는 최대한 적은 횟수로 기계를 돌려서 잔디를 깎고 싶습니다. Mirko가 지금까지 살펴본 모든 땅에 대해, Mirko는 땅의 모든 잔디를 깎기 위해 기계를 돌려야 하는 최소 횟수를 구하고 싶습니다. Mirko를 도와 이 문제를 풀어주세요.

--------

[입력]

1번째 줄에는 테스트 케이스의 개수 K (1 ≤ K ≤ 50 000)가 주어집니다.

다음 K개 줄에는 한 줄에 2개의 자연수 N, M (1 ≤ N, M ≤ 1 000 000)이 주어집니다.

--------

[출력]

Mirko가 살펴본 각 땅에 대해, 땅의 모든 잔디를 깎기 위해 기계를 돌려야 하는 최소 횟수를 한 줄씩 출력합니다.

댓글을 작성하려면 로그인해야 합니다.