You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡在心中想了一个 $[1,n]$ 的整数 $y$，同时给你一个代价数组 $a_1,a_2,\dots,a_n$。你需要猜出巡的数。你可以进行如下的询问：

• 询问 $x$：你需要交给巡 $a_x$ 的金币，然后巡会告诉你 $[y\leq x]$。

判断最劣情况下你需要多少金币才能知道巡心中的数。

输入格式

第一行一个正整数 $T$ 表示测试数据数目。

对每组测试数据，第一行一个正整数表示 $n$。第二行长度为 $n$ 的正整数列表示 $a_i$。

输出格式

$T$ 行，每行一个正整数表示答案。

样例 $1$

【样例输入】

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

【样例输出】

1
3
5
12
17

【样例解释】

对测试数据 $1$，花费 $1$ 的金币询问 $1$，可以判断出 $1,2$。

对测试数据 $2$，花费 $2$ 金币询问 $2$，可以区分 $\{1,2\}$ 和 $\{3\}$。然后花费 $1$ 金币询问 $1$ 能够区分 $\{1\}$ 和 $\{2\}$。

样例 $2$

见附加文件。

数据范围

对所有数据 $1\leq T\leq 10$，$1\leq n\leq 5000$，$1\leq a_i\leq 10^9$，$1\leq a_1\leq a_2\leq \dots\leq a_n\leq 10^9$。

特殊性质：$a_i=1$。