Description

在 Infinite House of Pancakes（无限煎饼屋），实际上只有有限数量的煎饼，但有无限多的食客愿意来吃！当餐厅早晨开门时，在无数食客中，恰好有 $D$ 位食客的盘子里有煎饼；第 $i$ 位食客的盘子里有 $P_i$ 块煎饼。其他所有人的盘子都是空的。

通常情况下，每过一分钟，每个盘子里有煎饼的食客会吃掉自己盘子中的一块煎饼。然而，有些分钟可能是“特殊分钟”。在特殊分钟里，主服务员会请大家注意，选择一位盘子里有煎饼的食客，从该食客的盘子中取出若干块煎饼，并将这些煎饼转移到另一位食客（无论其盘子是否为空）的盘子里。在特殊分钟里，没人会吃煎饼，因为那样太不礼貌了。

你是今天早上的主服务员，你需要决定哪些分钟（如果有的话）是特殊分钟，以及哪些煎饼要转移到哪里。也就是说，每一分钟，你可以选择什么都不做，让食客们吃煎饼，或者宣布这是一个特殊分钟，打断食客们，进行一次煎饼的转移操作，如上所述。

当所有煎饼都被吃完时，早餐结束。你能让早餐在最短的时间内结束吗？

Input Format

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试用例。每组测试用例包含两行，第一行为 $D$，表示盘子里有煎饼的食客数量，第二行为 $D$ 个用空格分隔的整数，分别表示这些食客盘子里的煎饼数量。

Output Format

对于每组测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是完成早餐所需的最少分钟数。

3
1
3
4
1 2 1 2
1
4

Case #1: 3
Case #2: 2
Case #3: 3

Hint

样例解释

在第 1 组样例中，一位食客一开始有 3 块煎饼，其他人的盘子都是空的。一种最优策略如下：

第 1 分钟：什么都不做。该食客吃掉一块煎饼。

第 2 分钟（特殊分钟）：打断，取出一块煎饼放到另一位空盘子的食客那里。（注意，无论有多少食客一开始有煎饼，总有无限多的空盘子可用。）

第 3 分钟：什么都不做。这两位食客各自吃掉最后一块煎饼。

在第 2 组样例中，最优策略是不进行任何打断，让食客们连续吃 2 分钟即可吃完所有煎饼。

在第 3 组样例中，一位食客一开始有 4 块煎饼，其他人的盘子都是空的。最优策略是在第 1 分钟进行一次特殊分钟，将两块煎饼分给另一位空盘子的食客，然后在第 2、3 分钟什么都不做，让两位食客各自吃掉剩下的煎饼。

数据范围

• $1 \leq T \leq 100$。

小数据集（9 分）

• 时间限制：240 5 秒。
• $1 \leq D \leq 6$。
• $1 \leq P_i \leq 9$。

大数据集（12 分）

• 时间限制：240 10 秒。
• $1 \leq D \leq 1000$。
• $1 \leq P_i \leq 1000$。

由 ChatGPT 4.1 翻译