심술쟁이 배틀십

동생과 함께 간단한 배틀십 게임을 한다. 판은 $R$행 $C$열인 직사각형 격자다. 게임이 시작되면 너는 눈을 감고, 게임이 끝날 때까지 뜨지 않는다. 동생은 $1 \times W$ 크기의 배 한 척을 판 위 어딘가에 가로로 놓는다. 배는 판 안에 완전히 들어가야 하고, 배의 각 칸은 격자의 한 칸을 정확히 차지하며, 회전할 수 없다.

각 차례에 너는 판의 칸 하나를 말하고, 동생은 그 칸이 명중인지 빗나감인지 답한다. 명중은 배가 차지한 칸이라는 뜻이다. 동생은 배의 어느 부분이 맞았는지는 알려주지 않고, 말한 칸에 배의 일부가 있는지만 알려준다. 너는 기억력이 완벽해서 동생이 지금까지 답한 내용을 모두 기억한다. 배가 차지한 칸을 모두 말하면 배가 침몰하고 게임이 끝난다. 점수는 그때까지 쓴 차례의 수이고, 점수는 낮을수록 좋다.

원래 배는 한 번 놓으면 움직이지 않아야 하지만, 심술궂은 동생은 원할 때마다 배의 위치를 몰래 바꾸려고 한다. 배가 계속 가로로 놓여 있고, 판 안에 완전히 들어가며, 새 위치가 지금까지 동생이 답한 내용과 모순되지 않기만 하면 된다. 예를 들어 1행 4열 판에 $1 \times 2$ 배가 있다고 하자. 동생은 처음에 배를 왼쪽 두 열에 놓을 수 있다. 네가 첫 차례에 (1, 2)를 말하면, 동생은 배를 오른쪽 두 열로 몰래 옮기고 (1, 2)는 빗나감이라고 답할 수 있다. 그러나 다음 차례에 네가 (1, 3)을 말하면, 그것도 빗나감이라고 답하면서 배를 원래 자리로 되돌릴 수는 없다. (1, 2)에 대해 앞서 한 답과 모순되기 때문이다.

너는 동생이 속인다는 것을 알고, 동생도 네가 그것을 안다는 것을 안다. 너는 점수를 최소로 만들고 동생은 점수를 최대로 만들도록 둘 다 최선을 다한다. 동생이 어떻게 하든 네가 반드시 보장할 수 있는 가장 낮은 점수는 얼마인가?

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에는 각각 세 정수 $R$, $C$, $W$가 공백으로 구분되어 주어진다. $R$은 판의 행 수, $C$는 판의 열 수, $W$는 배의 가로 길이다.

제한

• $1 \le T \le 100$
• $1 \le R \le 20$
• $1 \le W \le C \le 20$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 네가 보장할 수 있는 가장 낮은 점수다.

예제 입력의 첫 번째 케이스는 1행 4열 판에 $1 \times 2$ 배가 놓인 경우다. 최적 전략 하나는 (1, 2)를 먼저 말하는 것이다.

동생이 명중이라고 답하면 배의 나머지 한 칸은 (1, 1) 아니면 (1, 3)이므로 두 칸을 모두 말하면 된다. 나머지 칸을 먼저 정확히 짚더라도, 동생은 (1, 2)가 명중인 상태를 유지하는 자리로 배를 옮겨 빗나감이라고 답할 수 있다. 이미 명중이 나온 뒤에도 앞서 답한 내용과 모순되지 않으면 동생은 배를 옮길 수 있다.

동생이 빗나감이라고 답하면 모순 없는 배치는 (1, 3)과 (1, 4)를 차지하는 것 하나뿐이고, 그 뒤로 동생은 배를 옮길 수 없다. 그 두 칸을 말하면 된다.

어느 쪽이든 (1, 2) 다음 두 차례면 끝나므로 점수는 3이다. 두 차례로 끝내는 방법은 없다. 첫 칸을 어떻게 고르든 가로로 두 칸이 비어 있는 자리가 남고, 동생은 배를 그리로 옮겨 빗나감이라고 답한다. 아직 한 번도 맞지 않은 배를 남은 한 차례로 침몰시킬 수는 없다.

두 번째 케이스는 배가 행을 가득 채워서 동생이 배를 놓을 자리가 하나뿐이다. 모든 칸을 말하면 된다.

세 번째 케이스에서 동생은 $1 \times 1$ 배를 아직 말하지 않은 칸으로 언제든 옮길 수 있다. 그래서 10칸을 모두 말해야 하고, 마지막 칸에서야 명중이 나오면서 곧바로 침몰한다.