题目描述

Kelly is allergic to exactly one of $\mathrm{N}$ foods, but she isn't sure which one. So she decides to undergo some experiments to find out.

In each experiment, Kelly picks several foods and eats them all. She waits $\mathrm{A}$ days to see if she gets any allergic reactions. If she doesn't, she knows she isn't allergic to any of the foods she ate. If she does get a reaction, she has to wait for it to go away: this takes a total of $\mathrm{B}$ days (measured from the moment when she ate the foods).

To simplify her experimentation, Kelly decides to wait until each experiment is finished (after $\mathrm{A}$ or $\mathrm{B}$ days) before starting the next one. At the start of each experiment, she can choose the set of foods she wants to eat based on the results of previous experiments.

Kelly chooses what foods to eat for each experiment to minimize the worst-case number of days before she knows which of the $\mathrm{N}$ foods she is allergic to. How long does it take her in the worst case?

输入格式

The first line of the input gives the number of test cases, $\mathrm{T}$. $\mathrm{T}$ test cases follow. Each test case on a single line, containing three space-separated integers: $\mathrm{N}, \mathrm{A}$ and $\mathrm{B}$.

输出格式

For each test case, output one line containing "Case #x: y", where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is the number of days it will take for Kelly to find out which food she is allergic to, in the worst case.

3
4 5 7
8 1 1
1 23 32

Case #1: 12
Case #2: 3
Case #3: 0

提示

In the first sample case:

• First, Kelly eats foods #1 and #2.
• If she gets no reaction after 5 days, she eats food #3. 5 days after that, she will know whether she is allergic to food #3 or food #4.
• If she does get a reaction to the first experiment, then 7 days after the first experiment, she eats food #1. 5 days after that, she will know whether she is allergic to food #1 or food #2.

Limits

• $1 \leq T \leq 200$

Small dataset(15 Pts)

• Time Limit: 60 3 seconds
• $1 \leq N \leq 10^{15}$
• $1 \leq A\leq B \leq 100$

Large dataset(35 Pts)

• Time Limit: 120 5 seconds
• $1 \leq N \leq 10^{15}$
• $1 \leq A\leq B \leq 10^{12}$