Brattleship

당신은 남동생과 간소화된 "전함" 게임을 하려고 한다. 이 게임의 보드는 R개의 행과 C개의 열로 이루어진 직사각형 격자이다. 게임이 시작되면 눈을 감고 게임이 끝날 때까지 계속 감고 있어야 한다. 남동생은 직사각형 1 x W 크기의 배 하나를 보드 어딘가에 가로로 배치한다. 배는 항상 보드 안에 완전히 들어가야 하고, 배의 각 칸은 격자의 칸 정확히 하나를 차지해야 하며, 배를 회전할 수는 없다.

게임의 각 턴마다 당신은 보드의 칸 하나를 말하고, 남동생은 그 칸이 명중(배가 차지한 칸 중 하나)인지 빗나감인지 알려 준다. (남동생은 배의 어느 부분이 맞았는지는 말하지 않고, 당신이 말한 칸에 배의 일부가 있는지만 알려 준다.) 당신은 기억력이 완벽하며, 남동생이 알려 준 모든 정보를 추적할 수 있다. 배가 차지한 모든 칸을 말하면 게임이 끝나고(배가 침몰하고), 소요된 턴 수가 점수가 된다. 목표는 점수를 최소화하는 것이다.

배는 일단 배치된 뒤에는 움직이면 안 되지만, 말썽꾸러기인 남동생은 배가 가로 방향을 유지하고 보드 안에 완전히 들어가며 새 위치가 지금까지 자신이 알려 준 모든 정보와 일치하기만 하면 언제든 배의 위치를 바꾸는 부정행위를 할 계획이다. 예를 들어 1x4 보드와 1x2 배에서 남동생은 처음에 배가 가장 왼쪽의 두 열에 걸치도록 배치할 수 있다. 당신이 처음으로 행 1, 열 2을 추측했다면, 남동생은 몰래 배를 가장 오른쪽의 두 열로 옮기고 (1, 2)이 빗나갔다고 말할 수 있다. 하지만 그다음 추측이 (1, 3)이었다면, 남동생은 그것도 빗나갔다고 말하고 배를 원래 위치로 되돌릴 수 없다. 그렇게 하면 앞서 (1, 2)에 관해 말한 내용과 일치하지 않기 때문이다.

당신이 남동생의 부정행위를 알고 있을 뿐만 아니라, 남동생도 당신이 알고 있다는 사실을 안다. 두 사람 모두 최적으로 플레이한다면(당신은 점수를 최소화하고 남동생은 최대화한다면), 남동생이 무엇을 하든 달성을 보장할 수 있는 가장 낮은 점수는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ W ≤ C.

작은 데이터 세트

시간 제한: 240초. T = 55. R = 1. 1 ≤ C ≤ 10.

큰 데이터 세트

시간 제한: 480초. 1 ≤ T ≤ 100. 1 ≤ R ≤ 20. 1 ≤ C ≤ 20.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 공백으로 구분된 세 정수 R, C, W가 주어진다. 이들은 차례로 보드의 행 수, 열 수, 배의 너비이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 이때 x는 테스트 케이스 번호(1부터 시작)이고, y는 보장할 수 있는 최소 점수이다.

케이스 #1에서 보드는 한 개의 행과 네 개의 열로 이루어져 있고, 배는 한 개의 행과 두 개의 열을 차지한다. 최적 전략 중 하나는 먼저 (1, 2) 칸을 말하는 것이다.

남동생이 명중이라고 말하면 1x2 배의 나머지 칸은 (1, 1) 또는 (1, 3) 중 하나에 있어야 하므로, 두 칸을 모두 말하기만 하면 된다. 우연히 배의 나머지 부분이 있는 칸을 정확히 말했다면, 남동생은 (1, 2)이 여전히 명중인 상태로 당신의 추측이 빗나가도록 배의 위치를 바꿀 것이다. 새 위치가 자신이 이미 알려 준 정보와 일치하기만 하면, 남동생은 배가 명중된 뒤에도 여전히 배를 움직일 수 있다는 점에 유의하라.

남동생이 빗나감이라고 말하면, 일치하는 시나리오로는 배가 (1, 3)과 (1, 4)에 있는 경우만 남으며, 이제부터 남동생은 이를 바꿀 수 없다. 그 두 칸을 말하기만 하면 된다.

따라서 (1, 2)을 말한 뒤 남동생이 무엇을 하든, 그 후 두 번의 움직임을 더 사용해 총 세 번의 움직임으로 게임을 끝낼 수 있다.

또한 두 번의 움직임만으로 게임을 끝내는 것을 보장하는 것은 불가능하므로, 세 번의 움직임을 사용하는 해법이 최적이다. 일반성을 잃지 않고 첫 움직임을 하나 선택하자. 무엇을 선택하든 아직 비어 있는 1x2 영역이 남아 있으므로, 남동생은 그곳으로 배를 옮기고 빗나갔다고 주장할 수 있다. 아직 한 번도 명중하지 않은 그 배를 움직임 한 번만 더 사용해 침몰시키는 것은 불가능하다.

케이스 #2에서는 배가 보드를 완전히 채우므로 남동생이 배를 놓을 수 있는 위치는 하나뿐이다. 모든 칸을 말하기만 하면 된다.

케이스 #3에서는 남동생이 아직 시도하지 않은 칸으로 1x1 배를 언제든 옮길 수 있으므로, 10개의 칸을 모두 말해야 하며 마지막 칸에서야 마침내 명중하고 배를 즉시 침몰시킨다.