얄미운 동생의 배틀십

동생과 배틀십을 간단하게 바꾼 게임을 한다. 판은 $R$행 $C$열짜리 격자다. 게임이 시작되면 눈을 감고 끝날 때까지 뜨지 않는다. 동생은 $1 \times W$짜리 배 하나를 판 위 어딘가에 가로로 놓는다. 배는 판 안에 완전히 들어가야 하고, 배의 각 칸은 격자의 한 칸을 정확히 차지하며, 절대 회전하지 않는다.

매 차례마다 칸 하나를 부르면 동생은 그 칸이 명중인지 빗나감인지 답한다. 배의 어느 부분을 맞혔는지는 알려 주지 않는다. 기억력이 완벽해서 동생이 지금까지 준 답을 모두 기억한다. 배가 차지한 칸 $W$개를 모두 부르면 게임이 끝나고, 점수는 사용한 차례 수다. 점수를 최소로 만들고 싶다.

배는 한 번 놓으면 움직이지 않아야 하지만, 심술궂은 동생은 속임수를 쓸 생각이다. 배가 가로로 놓인 채 판 안에 완전히 들어가고 새 위치가 지금까지 준 답과 모순되지 않기만 하면, 동생은 언제든 배를 옮긴다. 예를 들어 $1 \times 4$ 판에 $1 \times 2$ 배가 있으면 동생은 처음에 배를 1열과 2열에 놓는다. 첫 질문이 1행 2열이면 동생은 배를 3열과 4열로 몰래 옮기고 빗나감이라고 답한다. 그러나 다음 질문이 1행 3열이면 거기서도 빗나감이라고 답하며 배를 원래 자리로 되돌릴 수는 없다. (1, 2)에 대해 한 말과 어긋나기 때문이다.

동생이 속인다는 사실을 알고, 동생도 내가 그것을 안다는 사실을 안다. 둘 다 최선으로 움직여서 나는 점수를 최소로, 동생은 점수를 최대로 만든다. 동생이 어떻게 하든 보장할 수 있는 가장 낮은 점수를 구하라.

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

제한

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

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

예제의 첫 번째 케이스에서 판은 1행 4열이고 배는 두 열을 차지한다. 최적 전략 하나는 (1, 2)를 먼저 부르는 것이다.

동생이 명중이라고 답하면 배의 나머지 한 칸은 (1, 1) 아니면 (1, 3)이므로 두 칸을 모두 부르면 된다. 나머지 한 칸이 실제로 있는 자리를 먼저 불러도, 동생은 (1, 2)가 여전히 명중이 되도록 배를 옮겨서 이번 질문을 빗나감으로 만든다. 명중이 나온 뒤에도 새 위치가 지금까지 한 말과 어긋나지 않으면 동생은 배를 옮긴다.

동생이 빗나감이라고 답하면 남는 위치는 3열과 4열뿐이고 동생은 더 이상 이를 바꾸지 못하므로, 그 두 칸을 부르면 된다.

어느 쪽이든 두 차례를 더 써서 끝나므로 모두 세 차례다. 세 차례가 최적이기도 하다. 두 차례로는 절대 보장할 수 없기 때문이다. 첫 질문을 무엇으로 잡든 $1 \times 2$ 크기의 빈 자리가 남고, 동생은 배를 그곳으로 옮긴 다음 빗나감이라고 답한다. 한 번도 맞지 않은 배를 남은 한 차례로 격침할 방법은 없다.

두 번째 케이스에서는 배가 판을 가득 채우므로 놓을 자리가 하나뿐이고, 모든 칸을 부르면 된다.

세 번째 케이스에서는 동생이 $1 \times 1$ 배를 아직 시도하지 않은 칸으로 매번 옮기므로, 10칸을 전부 부르고 마지막 칸에서야 유일한 명중이 나온다.