对于整数集合 $$$S$$$,将 $$$\operatorname{mex}(S)$$$ 定义为未出现在 $$$S$$$ 中的最小非负整数。
NIT,切割者,决定毁灭宇宙。他的实力不如灭霸,所以他只能打几个响指就毁灭宇宙。
Universe 可以表示为长度为 $$$n$$$ 的 1 索引数组 $$$a$$$。当NIT打响指时,他对阵列做了以下操作:
- 他选择正整数 $$$l$$$ 和 $$$r$$$ 使得 $$$1\le l\le r\le n$$$。设 $$$w=\operatorname{mex}(\{a_l,a_{l+1},\dots,a_r\})$$$。然后,对于所有 $$$l\le i\le r$$$,将 $$$a_i$$$ 设置为 $$$w$$$。
我们说宇宙被毁灭当且仅当对于所有$$$1\le i\le n$$$,$$$a_i=0$$$成立。
找出 NIT 需要打响指来摧毁宇宙的最少次数。也就是说,找到 NIT 需要执行的最少操作次数才能使数组中的所有元素等于 $$$0$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_n$$$ ($$$0\le a_i\le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入 #1
4 4 0 0 0 0 5 0 1 2 3 4 7 0 2 3 0 1 2 0 1 1000000000
输出 #1
0 1 2 1
注意
在第一个测试用例中,我们执行 $$$0$$$ 操作,并且数组中的所有元素都已经等于 $$$0$$$。
在第二个测试用例中,一种最佳方法是使用 $$$l=2$$$, $$$r=5$$$ 进行操作。
在第三个测试用例中,一种最佳方法是执行两次操作,分别使用 $$$l=4$$$、$$$r=4$$$ 和 $$$l=2$$$、$$$r=6$$$。
在第四个测试用例中,一种最佳方法是使用 $$$l=1$$$, $$$r=1$$$ 进行操作。