G1. 许愿卫星（简单版）
时间限制：每个测试点 4 秒
内存限制：512 兆字节

---

题目描述

这是该问题的简单版本。与困难版本的区别在于，本版本中 $t \le 1000$，$n \le 5000$，且所有测试用例的 $n$ 之和不超过 $5000$。只有解决了所有版本的用户才能进行 Hack。

对于一个非空序列 $c$，长度为 $k$，定义 $f(c)$ 如下：

Turtle 和 Piggy 在序列上玩游戏。他们拿到序列 $c_1, c_2, \dots, c_k$，Turtle 先手。Turtle 和 Piggy 轮流操作（Turtle 先，然后 Piggy，然后 Turtle，依此类推）。
游戏过程如下：

• 设当前序列长度为 $m$。如果 $m = 1$，游戏结束。
• 如果游戏未结束，且轮到 Turtle 操作，则 Turtle 必须选择一个整数 $i$ 满足 $1 \le i \le m-1$，令 $c_i = \min(c_i, c_{i+1})$，并删除 $c_{i+1}$。
• 如果游戏未结束，且轮到 Piggy 操作，则 Piggy 必须选择一个整数 $i$ 满足 $1 \le i \le m-1$，令 $c_i = \max(c_i, c_{i+1})$，并删除 $c_{i+1}$。

Turtle 希望最终 $c_1$ 的值尽可能大，Piggy 希望最终 $c_1$ 的值尽可能小。
$f(c)$ 为双方都采取最优策略时，游戏结束时 $c_1$ 的值。

对于一个长度为 $n$ 的排列 $p$，Turtle 定义排列的美丽值为：

$$\sum_{i=1}^{n} \sum_{j=i}^{n} f([p_i, p_{i+1}, \dots, p_j]) $$

即所有非空子段的 $f$ 值之和。

Piggy 给 Turtle 一个长度为 $n$ 的排列 $a$，其中部分元素缺失，用 $0$ 表示。

Turtle 希望确定一个长度为 $n$ 的排列 $b$，满足：

• $b$ 可以通过填充 $a$ 的缺失元素得到（即对所有 $1 \le i \le n$，若 $a_i \ne 0$，则 $b_i = a_i$）。
• 排列 $b$ 的美丽值最大。

你只需要求出这个最大的美丽值。

---

注：

• 长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个不同整数组成的数组，顺序任意。例如 $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现两次），$[1,3,4]$ 也不是（$n=3$ 却有 $4$）。
• 子段是指原序列中连续的一段（通过删除开头和结尾若干元素得到）。

---

输入格式

每个测试文件包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

接下来每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 5000$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$）。保证 $a$ 中不为 $0$ 的元素互不相同。

所有测试用例的 $n$ 之和不超过 $5000$。

---

输出格式

对于每个测试用例，输出一个整数 —— 最大的美丽值。

---

示例

输入

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

输出

4
12
11
44
110
300
45
40

---

样例解释

• 第一个测试用例：美丽值最大的排列是 $[1,2]$。其美丽值为： $f([1]) + f([2]) + f([1,2]) = 1 + 2 + 1 = 4$。
  对于 $c=[1,2]$，$f(c)=1$，因为 Turtle 只能选 $i=1$，他会让 $c_1 = \min(1,2)=1$。

• 第二个测试用例：一个最优排列是 $[3,2,1]$，美丽值为 $12$： $f([3]) + f([2]) + f([1]) + f([3,2]) + f([2,1]) + f([3,2,1]) = 3 + 2 + 1 + 2 + 1 + 3 = 12$。

• 第三个测试用例：一个最优排列是 $[2,1,3]$。

• 第四个测试用例：若 $c=[3,2,4,5,1]$，则 $f(c)=3$，过程示例见原题。

• 第五个测试用例：一个最优排列是 $[1,3,2,5,6,4,7]$。