多重集（multiset）是类似于集合的元素集合，其中元素可以重复出现。例如，以下是一个多重集：

$\{0, 0, 1, 2, 2, 5, 5, 5, 8\}$

给定一个定义在非负整数上的多重集 $S$，以及一个目标非负整数 $n$，使得 $n$ 不属于 $S$。你的目标是通过重复执行以下 3 步操作，将 $n$ 插入到 $S$ 中：

1. 选择 $S$ 的一个（可能为空的）子集 $T$。这里，$T$ 是 $S$ 中出现的不同数字组成的集合。
2. 从 $S$ 中删除 $T$ 中的元素。（每个元素仅删除一个副本。）
3. 将 $\text{mex}(T)$ 插入到 $S$ 中，其中 $\text{mex}(T)$ 是不属于 $T$ 的最小非负整数。$\text{mex}$ 代表“最小排除值”（minimum excluded value）。

你的目标是找到使 $n$ 成为 $S$ 的一部分所需的最少操作次数。

由于 $S$ 的大小可能很大，它将以大小为 $n$ 的列表 $(f_0, \dots, f_{n-1})$ 的形式给出，其中 $f_i$ 表示数字 $i$ 在 $S$ 中出现的次数。（回想一下，$n$ 是我们要插入到 $S$ 中的整数。）

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 200$)，表示测试用例的数量。每个测试用例由以下两行描述：

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

输出格式

对于每个测试用例，打印一行，包含满足条件所需的最少操作次数。

子任务

• 子任务 #1 (5 分)：$n \le 2$
• 子任务 #2 (17 分)：$n \le 20$
• 子任务 #3 (7 分)：$f_i = 0$
• 子任务 #4 (9 分)：$f_i \le 1$
• 子任务 #5 (20 分)：$f_i \le 2000$
• 子任务 #6 (9 分)：$f_0 \le 10^{16}$ 且 $f_j = 0$ (对于所有 $j \neq 0$)
• 子任务 #7 (10 分)：存在一个值 $i$ 使得 $f_i \le 10^{16}$ 且 $f_j = 0$ (对于所有 $j \neq i$)
• 子任务 #8 (23 分)：无附加限制

样例

输入 1

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

输出 1

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\}$