有人出不出题了，于是只能对着 NOI 题意做随机修改。

题目描述

已加粗和 [NOI2023] 合并书本 不同的部分

小 C 有 $n$ 本书，每本书都有一个重量，他决定把它们合并成一摞。

每一次合并小 C 可以把一摞书放到另一摞书上面，使得它们合并到一摞。如果小 C 把第 $i$ 摞书放到第 $j$ 摞书上面，小 C 需要消耗的体力为第 $i$ 摞书的磨损值加上两摞书的重量之和。

初始时每本书自成一摞且磨损值均为 $0$。每当小 C 将两摞书合并后，形成的新的一摞书的磨损值为合并前的两摞书的磨损值的较大值的两倍再加一，重量为合并前的两摞书的重量之和。

你的任务是设计出合并的次序方案，使小 C 耗费的体力最少，并输出这个最小的体力耗费值。

有多组数据。

输入格式

输入的第一行包含一个正整数 $t$，表示数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含一个正整数 $n$，表示有 $n$ 本书。

输入的第二行包含 $n$ 个正整数，第 $i$ 个数 $w_i$ 表示第 $i$ 本书的重量。

输出格式

对于每组测试数据输出一行一个整数，表示将 $n$ 本书合并成一摞需要消耗的最少体力。

样例

输入

5
6
1 1 4 5 1 4
6
10 10 40 50 10 40
5
1000000000 1000000000 1000000000 1000000000 1000000000
6
1 3 15 105 945 27455185
6
1 2 3 4 5 6

输出

38
371
12000000001
27457470
52

数据范围与约束

对于所有数据，有 $\sum n^2\leq 10^8；\sum n \leq 5\times 10^5;1\leq w_i\leq 10^9$。

共有 7 组 $subtask$，每组的特殊限制与分数如下：

$subtask1(5pts):n\leq 6,T\leq 5$

$subtask2(15pts):n\leq 12, T\leq 5$

$subtask3(15pts):n\leq 30,T\leq 5$

$subtask4(15pts):n\leq 80,T\leq 5$

$subtask5(20pts):\sum n^3\leq 5\times 10^7$

$subtask6(5pts):$ 同一组数据内的所有 $w_i$ 相同。

$subtask7(25pts):$ 无特殊限制。

评测时开启所有合理的子任务依赖。