Allergy Testing (Large)

Kelly is allergic to exactly one of $N$ foods, but she does not know which one, so she runs experiments to find out.

In one experiment Kelly picks a set of foods and eats all of them. Exactly $A$ days later she learns whether she reacted. If she did not react, she is not allergic to any food in that set. If she did react, the food she is allergic to is one of the foods in that set, and the reaction takes $B$ days to fade, counted from the moment she ate.

Kelly starts an experiment only after the previous one is completely over, so an experiment that causes no reaction occupies $A$ days and an experiment that causes a reaction occupies $B$ days. She picks the foods for each experiment after seeing the results of all earlier experiments.

The answer is the number of days until Kelly knows which food she is allergic to. Because a result arrives $A$ days after she eats, she never has to wait for the reaction of her last experiment to fade.

Kelly plays so that the worst case is as short as possible. How many days does she need in the worst case?

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three space separated integers $N$, $A$ and $B$.

Constraints

• $1 \le T \le 200$
• $1 \le N \le 10^{15}$
• $1 \le A \le B \le 10^{12}$

For each test case, print one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of days Kelly needs in the worst case to find out which food she is allergic to.

For $N = 4$, $A = 5$ and $B = 7$ the answer is 12.

• Kelly first eats foods 1 and 2.
• If there is no reaction after 5 days, she eats food 3. Five days after that she knows whether she is allergic to food 3 or food 4, so this branch ends on day 10.
• If the first experiment does cause a reaction, she eats food 1 seven days after the first experiment started. Five days after that she knows whether it is food 1 or food 2, so this branch ends on day 12.