说明

给定一个长 $n$ 的序列 $a$，不断进行如下操作：

1. $\forall i\in[1,n]$，令 $b_i$ 为集合 $\{a_1,a_2,a_3,\dots,a_i\}$ 的 $\text{mex}$（最小的未出现的非负整数）；
2. $\forall i\in[1,n]$，令 $a_i$ 变为 $b_i$；

求有多少种序列 $a$ 会在该过程中被生成（包含原序列即第 $0$ 轮操作结束后的序列）。两个长 $n$ 的序列 $a,b$ 不同当且仅当 $\exist i\in[1,n]$ 使得 $a_i\not=b_i$。

输入格式

第一行两个整数 $c,T$ 分别表示测试点所属的子任务编号（样例保证 $c=0$）和数据组数。

对于每组数据，输入两行：

• 第一行一个整数 $n$；

• 第二行 $n$ 个整数表示序列 $a$；

输出格式

对于每组数据，输出一行一个整数表示答案。

0 1
5
3 2 1 1 4

3

0 1
12
1 0 3 2 2 1 4 5 6 8 7 9

4

提示

【样例 1 解释】

这是前几轮操作的结果：

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

不难发现，之后序列 $a$ 会不断在全 $1$ 序列与全 $0$ 序列之间交替，故共有 $3$ 种序列 $a$ 会被生成，答案为 $3$。

【样例 2 解释】

这是前几轮操作的结果：

1 0 3 2 2 1 4 5 6 8 7 9
0 2 2 4 4 4 5 6 7 7 9 10
1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1

【数据范围】

对于所有测试数据，$1\le n,\sum n\le 10^6$，$0\le a_i\le n$，$1\le T\le 100$。