Kelly 对 $N$ 种食物中的恰好一种过敏，但她不确定是哪一种。因此，她决定进行一些实验来找出答案。

在每次实验中，Kelly 会挑选几种食物并全部吃掉。她会等待 $A$ 天来观察是否出现过敏反应。如果没有反应，她就知道她对所吃的这些食物都不过敏。如果出现了反应，她必须等待反应消失：这总共需要 $B$ 天（从她吃下食物的那一刻起计算）。

为了简化实验，Kelly 决定在开始下一次实验之前，先等待当前实验结束（$A$ 天或 $B$ 天后）。在每次实验开始时，她可以根据之前实验的结果选择要吃的食物集合。

Kelly 为每次实验选择要吃的食物，以最小化她在确定对 $N$ 种食物中的哪一种过敏之前所需的最坏情况天数。请问在最坏情况下，这需要多长时间？

样例

输入格式 1

3
4 5 7
8 1 1
1 23 32

输出格式 1

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

说明

在第一个样例中：

• 首先，Kelly 吃掉食物 #1 和 #2。
• 如果 5 天后没有反应，她接着吃食物 #3。在那之后 5 天，她就能知道她是对比食物 #3 还是食物 #4 过敏。
• 如果她在第一次实验中出现了反应，那么在第一次实验后的 7 天，她吃下食物 #1。在那之后 5 天，她就能知道她是对比食物 #1 还是食物 #2 过敏。