在数学，更具体地在图论中，树是一个无向图，其中任意两个节点之间恰好有一条路径相连。换句话说，任何没有简单环的连通图都是一棵树。

你在回家的路上发现了一棵部分树。这棵树有 $n$ 个节点，但缺少了 $n-1$ 条边。你想要通过添加 $n-1$ 条边来补全这棵树。添加后，任意两个节点之间必须恰好存在一条路径。众所周知，补全这棵树的方法有 $n^{n-2}$ 种，而你希望使补全后的树尽可能“酷”。一棵树的“酷度”是其所有节点酷度之和。一个节点的酷度为 $f(d)$，其中 $f$ 是一个预定义的函数，$d$ 是该节点的度数。补全后的树的最大酷度是多少？

输入格式

第一行包含一个整数 $T$，表示测试用例的总数。每个测试用例以一个整数 $n$ 开始，随后一行包含 $n-1$ 个整数 $f(1), f(2), \dots, f(n-1)$。

• $1 \le T \le 2015$
• $2 \le n \le 2015$
• $0 \le f(i) \le 10000$
• 至多有 10 个测试用例满足 $n > 100$。

输出格式

对于每个测试用例，请在一行中输出补全后的树的最大酷度。

样例

输入 1

2
3
2 1
4
5 1 4

输出 1

5
19