题目描述

题目译自 European Girls' Olympiad in Informatics 2022 Day1 T1. SubsetMex

多重集合是一个类似集合的元素集合，其中元素可以重复出现。例如，以下是一个多重集合：$\{0,0,1,2,2,5,5,5,8\}$。

给定一个由非负整数构成的多重集合 $S$ 和一个不在 $S$ 中的目标非负整数 $n$，你的目标是通过重复以下三步操作，将 $n$ 插入到 $S$ 中：

1. 从 $S$ 中选择一个（可能为空的）子集 $T$。这里的 $T$ 是一个由 $S$ 中出现的不同数字组成的集合。
2. 从 $S$ 中删除 $T$ 的元素。（每个元素只删除一次。）
3. 将 $\operatorname{mex}(T)$ 插入到 $S$ 中，其中 $\operatorname{mex}(T)$ 是 $T$ 中不包含的最小非负整数。Mex 表示最小排除值（minimum excluded）。

你的目标是找出使 $n$ 成为 $S$ 中元素所需的最小操作次数。

由于 $S$ 可能很大，它将以一个长度为 $n$ 的列表 $\left(f_0, \ldots, f_{n-1}\right)$ 的形式给出，其中 $f_i$ 表示数字 $i$ 在 $S$ 中出现的次数。（注意，$n$ 是我们试图插入到 $S$ 中的整数。）

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 200)$，表示测试数据的数量。接下来的每两行描述一组测试数据：

• 每组的第一行包含一个整数 $n$ $(1 \leq n \leq 50)$，表示要插入到 $S$ 中的整数。
• 每组测试数据的第二行包含 $n$ 个整数 $f_0, f_1, \ldots, f_{n-1}$ $(0 \leq f_i \leq 10^{16})$，表示上述多重集合 $S$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示满足条件所需的最小操作次数。

样例

输入

2
4
0 3 0 3
5
4 1 0 2 0

输出

4
10

初始时，$S = \{1,1,1,3,3,3\}$，目标是让 $4$ 出现在 $S$ 中。可以按以下步骤操作：

1. 选择 $T = \{\}$，则 $S$ 变为 $\{0,1,1,1,3,3,3\}$。
2. 选择 $T = \{0,1,3\}$，则 $S$ 变为 $\{1,1,2,3,3\}$。
3. 选择 $T = \{1\}$，则 $S$ 变为 $\{0,1,2,3,3\}$。
4. 选择 $T = \{0,1,2,3\}$，则 $S$ 变为 $\{3,4\}$。

数据范围与提示

详细子任务附加限制及分值如下表所示。