Brattleship

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

On every turn you name one cell, and your brother answers hit if the ship occupies that cell and miss otherwise. He never says which part of the ship you hit. Your memory is perfect, so you keep track of every answer he has given. The game ends once you have named all $W$ cells the ship occupies, and your score is the number of turns you used. You want your score to be as small as possible.

A ship is not supposed to move once it is placed, but your brother is a brat and plans to cheat. He moves the ship whenever he wants, as long as it stays horizontal, stays entirely on the board, and its new position agrees with every answer he has already given. For example, on a $1 \times 4$ board with a $1 \times 2$ ship he may start with the ship on columns 1 and 2. If your first guess is row 1, column 2, he can quietly slide the ship to columns 3 and 4 and answer miss. If your next guess is row 1, column 3, he can no longer answer miss and slide the ship back, because that would contradict what he said about (1, 2).

He cheats, you know he cheats, and he knows that you know. Both of you play optimally, you to minimize your 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 of the board, and the width of the ship.

Limits

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

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

In the first case of the example the board has one row and four columns, and the ship covers two columns. One optimal strategy starts by naming cell (1, 2).

If your brother answers hit, the rest of the ship sits in either (1, 1) or (1, 3), so you name both. If you happen to name the cell that really holds the rest of the ship, he slides the ship so that (1, 2) is still a hit and your new guess is a miss. He may still move the ship after a hit, as long as the new position agrees with what he has already said.

If he answers miss, the only position left is columns 3 and 4, and he can no longer change it, so you name those two cells.

Either way you finish in two more turns, for a total of three. Three is also optimal, because two turns can never be enough. Whatever your first guess is, a free $1 \times 2$ area is left over, your brother moves the ship there and calls your guess a miss, and one more turn cannot sink a ship that has not been hit at all.

In the second case the ship fills the whole board, so there is only one place for it and you simply name every cell.

In the third case your brother moves the $1 \times 1$ ship to some cell you have not tried yet every time, so you name all 10 cells and get the only hit on the last one.