你有 $$$n$$$ 根棍子,其中第 $$$i$$$ 根棍子的长度为 $$$a_i$$$。您想要选择这些棒的非空子集并将它们用作多边形的边。每个选定的棒必须完全用作多边形的单边。它是 不 允许将两根或多根棍子首尾相连并平行连接以形成更长的边。
您的目标是形成一个对称、严格凸且非退化的多边形:
- 对称:存在一条对称线,使得当多边形沿这条线折叠时,两半完全重合。
- 严格凸:其所有内角严格小于 $$$180^\circ$$$。
- 非退化:没有两个连续的边至少部分重合,没有边的长度为零,并且没有角度等于 $$$180^\circ$$$。
在您可以用棍子形成的所有此类多边形中,找到最大可能的周长$$$^{\text{*}}$$$。如果不存在有效的多边形,则输出$$$0$$$。
$$$^{\text{*}}$$$多边形的周长等于其边长之和。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3\le n\le 2\cdot 10^5$$$) — 木棍的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) - 木棍的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,表示可以从棍子的非空子集形成的非退化、对称和严格凸多边形的最大可能周长。如果不可能,则输出$$$0$$$。
示例
输入复制
535 5 734 5 735 5 1074 3 5 1 5 3 342 3 5 7
输出复制
1700230
注意
在第一个测试用例中,您可以使用所有三根棍子形成一个等腰三角形。它沿垂直虚线对称(见左图)。周长等于其边长之和:$$$5 + 5 + 7 = 17$$$。
在第二个测试用例中,所有三根棍子形成的三角形不对称(见右图)。可以证明,任何非空的棒子集都不能形成对称的、非退化的凸多边形。

在第三个测试用例中,不可能形成非退化多边形。如果使用所有三个边,则长度为 $$$5$$$ 的两条边与长度为 $$$10$$$ 的边重合,仅生成一条面积为零的直线。
在第四个测试用例中,我们可以使用三根长度为 $$$3$$$ 的棍子、两根长度为 $$$5$$$ 的棍子和一根长度为 $$$4$$$ 的棍子形成对称凸多边形(见左图)。长度为 $$$1$$$ 的最后一根棒不能包含在内,因为生成的多边形将不再对称(见右图)。

在第五个测试用例中,不允许将长度为 $$$2$$$ 和 $$$3$$$ 的棍子连接起来形成长度为 $$$5$$$ 的棍子(这将产生第一个测试用例)。可以证明,任何非空的棒子集都不能形成对称的、非退化的凸多边形。