题目描述

Evirir 这条龙潜入了一个巫师的城堡，并发现了一个神秘的装置。由于它爱玩的天性，它开始摆弄（破坏）这个装置……

Evirir 这条龙发现了一个由 $n$ 个非负整数组成的数组 $a_1, a_2, \ldots, a_n$。

在一次操作中，它可以选择一个非空的子数组 $^{\text{∗}}$ $b$ 并将其替换为整数 $\operatorname{mex}(b)$ $^{\text{†}}$ 。它希望使用任意多次操作，使数组 $a$ 只包含零。可以证明，在问题的约束条件下，这总是可能的。

需要找到使数组 $a$ 只包含零所需的最小操作次数。

• $^{\text{∗}}$ 如果可以通过删除开头和结尾的若干（可能为零或全部）元素来获得数组 $c$，则数组 $c$ 是数组 $d$ 的子数组。
• $^{\text{†}}$ 一个整数集合 $f_1, f_2, \ldots, f_k$ 的最小排除值（mex）定义为集合 $f$ 中不存在的最小的非负整数 $x$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 200$）。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$），即数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 100$）。

保证所有测试用例中 $n$ 的总和不超过 $500$。

输出格式

对于每个测试用例，输出一行一个整数，即使数组 $a$ 只包含零所需的最小操作次数。

说明/提示

在第一个测试用例中，Evirir 可以选择子数组 $b = [1, 2, 3]$ 并将其替换为 $\operatorname{mex}(1, 2, 3) = 0$，将数组 $a$ 从 $[0, \underline{1, 2, 3}]$ 变为 $[0, 0]$（其中选定的子数组已加下划线）。因此，答案是 $1$。

在第二个测试用例中，数组 $a$ 已经只包含 $0$，所以不需要进行任何操作。

在第三个测试用例中，Evirir 可以按如下方式更改 $a$：$[1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0]$。这里，$\operatorname{mex}(0, 1, 0, 1) = 2$ 和 $\operatorname{mex}(1, 2) = 0$。

在第四个测试用例中，Evirir 可以选择整个数组 $a$ 作为 $b$，将数组 $a$ 从 $[\underline{3, 1, 4, 1, 5}]$ 变为 $[0]$。

样例

10
4
0 1 2 3
6
0 0 0 0 0 0
5
1 0 1 0 1
5
3 1 4 1 5
4
3 2 1 0
7
9 100 0 89 12 2 3
4
0 3 9 0
7
0 7 0 2 0 7 0
1
0
2
0 1

1
0
2
1
1
2
1
2
0
1