随着在线购物的发展，物流行业与商品运输的联系日益紧密，行业繁荣带来了对大量员工的需求。因此，卡车司机 Alex 在他的日常工作中，需要将仓库中散落的多个包裹运送到其他城市。

根据高速公路运输的官方安全要求，Alex 必须将所有包裹捆绑紧实，以便安全地将货物固定在卡车上。Alex 知道，捆绑包裹所需的绳索长度取决于包裹本身的大小。此外，$n$ 个包裹在经过 $n-1$ 次捆绑后可以被妥善固定。而且，在捆绑货物时，为了避免散落，Alex 每次只能捆绑两个包裹。由于日常绳索消耗巨大，且需要 Alex 自费购买，他希望用最短的绳索长度捆绑所有货物。

例如，有 4 个包裹，大小分别为 8、5、14 和 26。如果 Alex 先将前两个捆绑在一起，所需的绳索长度为 13 ($8+5 = 13$)，而捆绑后两个包裹所需的绳索长度为 40 ($14+26 = 40$)。如果 Alex 继续将这两个捆绑物捆在一起，他所需的绳索长度将为 53 ($13+40 = 53$)。因此，这 4 个包裹的总绳索长度为 106 ($13+40+53 = 106$)。如果 Alex 尝试另一种方式，先捆绑前两个 ($8+5 = 13$)，加上第三个 ($13+14 = 27$)，然后再捆绑最后一个 ($27+14 = 53$)，他总共只需要长度为 93 ($13+27+53 = 93$) 的绳索。现在你的任务是帮助 Alex 找到所需绳索的最小长度。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例包含两行。第一行包含一个正整数 $n$，表示包裹的数量。第二行包含 $n$ 个正整数，由空格分隔，表示每个包裹的大小。

输出格式

对于每个测试用例，输出将所有包裹捆绑在一起所需的最小绳索长度，每个结果占一行。

数据范围

• $1 \le T \le 10$
• $1 \le n \le 1000$
• 每个包裹的大小不超过 1000。

样例

样例输入 1

4
6
2 3 4 4 5 7
5
5 15 40 30 10
10
3 1 5 4 8 2 6 1 1 2
9
3 2 1 6 5 2 6 4 3

样例输出 1

63
205
100
98