Description

今晚是歌剧的首演，你的朋友是女主角（首席女歌手）。你不会在观众席中，但你希望确保她能获得全场起立鼓掌——让每一位观众都站起来为她鼓掌。

最初，所有观众都坐着。每位观众都有一个“害羞等级”。害羞等级为 $S_i$ 的观众会等到至少有 $S_i$ 位其他观众已经站起来鼓掌后，才会立即站起来鼓掌。如果 $S_i = 0$，那么这位观众会无论如何都立刻站起来鼓掌。例如，害羞等级为 $S_i = 2$ 的观众一开始会坐着，只有在看到至少有两个人已经站起来鼓掌后，她才会站起来鼓掌。

你知道所有观众的害羞等级，并且你可以邀请额外的朋友加入观众席，以确保最终所有人都能站起来鼓掌。你可以为这些朋友分配任意害羞等级，不必相同。请问你至少需要邀请多少位朋友，才能保证全场起立鼓掌？

Input Format

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试数据。每组测试数据包含一行，首先是一个整数 $S_{\text{max}}$，表示观众中最害羞的人的害羞等级，然后是一个长度为 $S_{\text{max}} + 1$ 的数字字符串。该字符串的第 $k$ 个数字（从 0 开始计数）表示有多少位观众的害羞等级为 $k$。例如，字符串 "409" 表示有 4 位观众的害羞等级为 0，9 位观众的害羞等级为 2（害羞等级为 1 及其他等级的人数为 0）。注意，每个害羞等级的人数范围始终在 0 到 9 之间。

该字符串不会以 0 结尾。这意味着观众中至少有一人。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你需要邀请的最少朋友数。

4
4 11111
1 09
5 110011
0 1

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 0

Hint

样例解释

在第 1 组样例中，观众最终会自行完成全场起立鼓掌，无需你邀请任何人——首先害羞等级为 0 的观众会站起来，然后害羞等级为 1 的观众会站起来，依此类推。

在第 2 组样例中，必须邀请一位害羞等级为 0 的朋友，但这样就足以让所有观众都站起来。

在第 3 组样例中，一种最优方案是添加两位害羞等级为 2 的观众。

在第 4 组样例中，只有一位观众，他会立刻站起来。无需邀请任何朋友。

数据范围

• $1 \leq T \leq 100$。

小数据集（7 分）

• 时间限制：5 秒。
• $0 \leq S_{\text{max}} \leq 6$。

大数据集（10 分）

• 时间限制：10 秒。
• $0 \leq S_{\text{max}} \leq 1000$。

由 ChatGPT 4.1 翻译