你居住的城市里有很多高层建筑。由于城市规划的规定，每栋建筑的高度都是唯一的。有一天，你去了城外的山上。经过长途跋涉，你俯瞰这座城市，欣赏它的美景。在那里，你注意到了一些奇怪的事情，实际上是两件非常奇怪的事情。第一件事是，从特定的角度看，所有的建筑看起来都在一条直线上。另一件事是，这些建筑形成了多个不同寻常的“金字塔状”图案，且相邻的两个组之间有小间隙。同一组内的相邻建筑之间没有空隙。

一个由 $2k + 1$ 栋建筑组成的组（其中 $k$ 是正整数）如果满足以下条件，则可以形成金字塔状图案。假设按从左到右的顺序，建筑的高度分别为 $h_1, h_2, \dots, h_{2k+1}$。那么该组建筑需要满足 $h_1 < h_2 < \dots < h_k < h_{k+1} > h_{k+2} > \dots > h_{2k} > h_{2k+1}$。也就是说，先有 $k$ 栋高度递增的建筑，接着是该组中最高的建筑，然后是 $k$ 栋高度递减的建筑。城市由若干个这样的金字塔状图案组成（相邻组之间有小间隙）。这使得城市的轮廓非常独特且美观。假设同一组内的相邻建筑之间没有可见的间隙。

下图展示了两个城市的例子。第一个例子包含一个由 5 栋建筑组成的金字塔状图案。第二个例子总共有 6 栋建筑，包含两个金字塔状图案。

示例城市。

当你作为游客去到另一座城市时，你注意到那里的建筑也排列在一条直线上，相邻建筑之间没有间隙，但它们可能没有被分组为金字塔状图案。太可怕了！！现在，假设你有两台机器，分别叫“建筑交换机 2000”（Building Swapper 2000）和“分组制造机 3000”（Group Maker 3000）。“建筑交换机 2000”可以交换两栋相邻的建筑，但需要消耗 1 单位燃料。同样，“分组制造机 3000”可以将建筑分成一个或多个组，使得相邻的两个组之间有一点空间，但它是太阳能驱动的，因此不需要任何燃料。现在，你必须按顺序执行以下两个步骤：

• 使用“分组制造机 3000”将建筑分成大小为大于 2 的奇数的组。执行此步骤后，将会有若干个建筑组（此时可能还不是金字塔状），且相邻的两个组之间有小间隙。
• 使用“建筑交换机 2000”交换相邻建筑，直到每个组都变成金字塔状。你只能交换属于同一组的相邻建筑。

最终，你将得到若干个建筑组，它们都呈金字塔状，城市将拥有美观的轮廓。你的任务是计算实现这一目标所需的最小燃料消耗。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含一个整数 $N$ ($3 \le N \le 1000, N \neq 4$)，表示城市中建筑的数量。下一行包含 $N$ 个整数，表示建筑的高度 ($1 \le h_i \le 10^9$)。保证所有测试用例中 $N$ 的总和不超过 10000，且在每个测试用例中，所有建筑的高度都是唯一的。

输出格式

对于每个测试用例，输出一个整数，表示所需的最小燃料消耗。可以证明，在上述限制条件下，总能通过排列建筑来实现目标。

样例

样例输入 1

4
3
1 3 2
6
1 2 4 8 16 32
5
1 2 3 4 5
7
6 4 2 1 3 5 7

样例输出 1

0
2
3
9