Bulletproof Glass Testing Budget

Your boss thinks his life is in danger, so he had bulletproof glass fitted to his car. He doubts that the glass is really bulletproof. He fired one shot from $F$ feet away and the glass held, but he does not know whether it holds at a shorter range.

The glass has an unknown limit $D$. A bullet fired from $D$ feet or farther cannot break it, and a bullet fired from closer than $D$ feet breaks it. The shot from $F$ feet did not break the glass, so $0 \le D \le F$. This $D$ is the value your boss wants.

Testing happens at whole feet only. One bullet costs $B$. When a shot breaks the glass, replacing that pane costs another $G$, and the replacement costs the same even if no further shot is needed. A pane that survives a shot is shot at again as it is.

Firing from $F-1$ feet down to $0$ feet one foot at a time settles $D$ and breaks at most one pane, so it costs at most $F \times B + G$. Breaking more glass to save bullets is sometimes cheaper.

The testing has to determine $D$ whatever position the glass breaks at. Find the smallest budget that covers the worst case.

The first line has the number of test configurations $N$ ($1 \le N \le 100$).

Each of the next $N$ lines has three integers $F$, $G$ and $B$ separated by spaces. $F$ is the distance at which the glass is known to hold ($1 \le F \le 1000$), $G$ is the price of one pane of glass ($1 \le G \le 1000$), and $B$ is the price of one bullet ($1 \le B \le 100$).

For each test configuration print Case #n: first, then the smallest budget needed for the testing of that configuration. Here $n$ is the number of the configuration, counted from $1$ in input order.