考虑$dp[i][j]$表示最后一个为$j$,最后一段区间从$j$开始的最大$MEX$和,$g[i][j]$表示区间$(i,j)$的$MEX$那么转移分为两种: 第一种

dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - g[j][i] + g[j][i + 1]) 表示延续当前区间

第二种

dp[i+1][i+1]=max(dp[i+1][i+1],dp[i][j]+g[i+1][i+1])表示新开一个区间

题目内容

小红有一个长度为$n$的数组［$a1，a2，..，an$］，他希望将数组切分为若干段，使得每一段的$MEX$求和尽可能大。 数组的$MEX$定义为没有出现在数组中的最小非负整数，例如，$MEX[1,2,3]=0$,$MEX[1,0,3] =2$

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数$T$($1≤T≤100$)代表数据组数，

每组测试数据描述如下：

第一行输入一个整数$n$($1≤n≤2000$)代表数组中的元素数量。

第二行输入$n$个整数$a1，a2，..，an$($0≤a_i≤n)$代表数组元素。 除此之外，保证所有的$n$之和不超过$2000$。

输出描述

在一行上输出一个整数，代表每一段的$MEX$之和。

样例1

输入

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

输出

4
4

说明

对于第一组测试数据，切分成$[0，1]$和$[1，0]$两个数组，由于$MEX{0，1}=2$，所以答案为$4$。可以证明没有更大的答案。