题目描述

定义 $\operatorname{mex}$ 为一个集合中最小的没有出现过的非负整数。

给定一个由 $n$ 个非负整数组成的的序列 $a$，NIT 可以进行若干次操作，每次操作选择 $l$ 和 $r$（$1\le l \le r \le n$），将 $a_l, a_{l+1} \cdots a_r$ 全部修改为 $\operatorname{mex}(\{a_l, a_{l+1} \cdots a_r\})$。本题有多组数据，对于每一组数据，请回答 NIT 最少需要多少次操作可以让整个序列都为 $0$。

输入格式

第一行一个整数 $T$，表示有 $T$ 组询问。

对于每一组询问，第一行一个整数 $n$，表示序列长度，第二行 $n$ 个整数，表示这个序列。

输出格式

共 $T$ 行，每行一个整数，表示对应一组询问的答案。

样例解释

对于第一个测试样例，不要操作。

对于第二个测试样例，需要一次操作，选择 $l=2,r=5$。

对于第三个测试样例，需要两次操作，可以第一次选择 $l=4,r=4$，第二次选择 $l=2,r=6$。

对于第四个测试样例，需要一次操作，选择 $l=1,r=1$。

说明/提示

$1 \le t \le 10^4$，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$，$\sum n \le 2 \cdot 10^5$。

样例

4
4
0 0 0 0
5
0 1 2 3 4
7
0 2 3 0 1 2 0
1
1000000000

0
1
2
1