Brattleship

You are playing a simplified battleship game with your little brother. The board is a rectangular grid with $R$ rows and $C$ columns. When the game starts you close your eyes, and you keep them closed until the game ends. Your brother takes a single $1 \times W$ ship and places it horizontally somewhere on the board. The ship must fit entirely on the board, each cell of the ship covers exactly one grid cell, and the ship is never rotated.

On each turn you name a cell of the board, and your brother answers hit or miss. A hit means the ship covers that cell. He does not say which part of the ship was hit, only whether the named cell holds a part of the ship. Your memory is perfect, so you remember every answer he has given. Once you have named every cell the ship covers, the ship is sunk and the game ends. Your score is the number of turns you used, and a lower score is better.

The ship is not supposed to move once it is placed, but your brother is a brat and plans to change its position secretly whenever he likes. The ship only has to stay horizontal, stay entirely on the board, and sit in a position that does not contradict any answer he has given so far. Take a board with 1 row and 4 columns and a $1 \times 2$ ship. He can start with the ship on the two leftmost columns. If your first turn is (1, 2), he can slide the ship to the two rightmost columns and answer that (1, 2) is a miss. If your next turn is (1, 3), he cannot answer miss again and slide the ship back, because that contradicts his earlier answer about (1, 2).

You know that your brother cheats, and he knows that you know. You both play optimally, you to minimize the score and he to maximize it. What is the lowest score you can guarantee no matter what he does?

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $R$, $C$, and $W$ separated by spaces: the number of rows of the board, the number of columns, and the width of the ship.

Limits

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

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the lowest score you can guarantee.

The first case of the sample input has a board with 1 row and 4 columns and a $1 \times 2$ ship. One optimal strategy starts by naming (1, 2).

If your brother answers hit, the other cell of the ship is either (1, 1) or (1, 3), so you name both. Even if you pick the right one first, he can move the ship to a position that keeps (1, 2) a hit and answer miss. He may move the ship after a hit as long as the new position agrees with every answer he has already given.

If he answers miss, the only placement left covers (1, 3) and (1, 4), and after that he cannot move the ship. You name those two cells.

Either way you finish two turns after (1, 2), for a score of 3. Two turns are not enough. Whichever cell you name first, a horizontal run of two free cells remains, your brother moves the ship there and answers miss, and one remaining turn cannot sink a ship that has never been hit.

In the second case the ship fills the row, so your brother has only one place to put it and you name every cell.

In the third case your brother can move the $1 \times 1$ ship to any cell you have not named yet. You have to name all 10 cells, and the hit, which sinks the ship at once, comes only on the last one.