Description

Kelly 对某种食物过敏，但她不确定是哪一种。在她面前有 $\mathrm{N}$ 种不同的食物，而她恰好只对其中一种过敏。为了找出是哪一种，她决定进行一系列实验。

在每次实验中，Kelly 会选择若干种食物一起食用。然后她会等待 $\mathrm{A}$ 天，以观察自己是否会出现过敏反应：

• 如果没有反应，她就可以确定自己不对这些食物中的任意一种过敏；
• 如果出现了反应，她就必须等待反应完全消退，整个过程总共需要 $\mathrm{B}$ 天（从食用食物的那一刻算起）。

为简化实验安排，Kelly 决定：每次实验必须在上一次实验完全结束（无论是等待 $\mathrm{A}$ 天或 $\mathrm{B}$ 天）后才能进行。

在每次实验开始前，Kelly 可以根据之前实验的结果自由选择这一次要食用的食物集合。

她希望设计一套实验策略，在最坏情况下，也能尽可能快地确定自己对哪一种食物过敏。

请你计算：在最坏情况下，Kelly 最少需要多少天才能确定她对哪一种食物过敏？

Input Format

第一行是测试用例个数 $\mathrm{T}$。接下来是 $\mathrm{T}$ 个测试用例。

每个测试用例占一行，包含三个用空格分隔的整数 $\mathrm{N}, \mathrm{A}, \mathrm{B}$，分别表示食物总数、无过敏反应等待天数、以及有过敏反应时总的等待天数。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Kelly 在最坏情况下确定过敏源所需的总天数。

3
4 5 7
8 1 1
1 23 32

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

Hint

在第一个样例中：

• 第一次实验：吃食物 #1 和 #2；
• 如果 5 天后无反应，则进行第二次实验，吃食物 #3；
  • 再等 5 天后，如果无反应，则说明过敏的是食物 #4；
  • 如果有反应，则在第 10 天得知自己过敏于食物 #3；
• 如果第一次实验后出现过敏反应，那么在第 7 天（反应消退）后进行第二次实验，吃食物 #1；
  • 再过 5 天，无反应说明是食物 #2 过敏，有反应说明是食物 #1；
• 因此，最坏情况下是第 12 天得出结论。

限制条件

• $1 \leq T \leq 200$

Small 数据集（15 分）

• 时间限制：60 3 秒
• $1 \leq N \leq 10^{15}$
• $1 \leq A \leq B \leq 100$

Large 数据集（35 分）

• 时间限制：120 5 秒
• $1 \leq N \leq 10^{15}$
• $1 \leq A \leq B \leq 10^{12}$

翻译由 ChatGPT-4o 完成