题目描述

给定 $n$ 根棍子，第 $i$ 根棍子的长度为 $a_i$。你想从这些棍子中选择一个非空子集，将所选棍子分别作为多边形的边（每根棍子必须整体作为一条边，不能将多根棍子端对端拼接成更长的一条边）。要求构成的多边形满足以下三条性质：

• 对称（Symmetrical）：存在一条对称轴，使得沿该直线折叠后两半完全重合；
• 严格凸（Strictly convex）：所有内角均严格小于 $180^\circ$；
• 非退化（Non-degenerate）：没有相邻两条边部分重合、没有长度为 $0$ 的边、没有角为 $180^\circ$。

在所有满足上述条件的可构成多边形中，求能获得的最大周长（即所选边长之和）。若不存在任何合法多边形，输出 $0$。

输入格式

• 第 $1$ 行包含一个整数 $t$，表示测试用例个数（$1\le t\le 10^4$）。

• 随后按测试用例给出，每个测试用例包含两行：

  • 第一行一个整数 $n$（$3\le n\le 2\cdot 10^5$）——棍子数量。
  • 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每根棍子的长度（$1\le a_i\le 10^9$）。

• 输入中所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数：能构成的满足条件的多边形的最大周长；若无法构成则输出 0。

样例输入

5
3
5 5 7
3
4 5 7
3
5 5 10
7
4 3 5 1 5 3 3
4
2 3 5 7

样例输出

17
0
0
23
0

说明

样例解释

• 第一个样例：可以用三根棍子 $5,5,7$ 构成一个等腰三角形，满足对称且凸，周长 $5+5+7=17$。

• 第二个样例：无法从任意非空子集中构成对称且严格凸且非退化的多边形。

• 第三个样例：三根棍子 $5,5,10$ 不能构成非退化多边形（两边长度之和等于第三边，退化为一条直线）。

• 第四个样例：可以选用三根长度 $3$、两根长度 $5$ 和一根长度 $4$（共 $6$ 边）构成对称、严格凸的多边形，周长为 $3+3+3+5+5+4=23$；长度为 $1$ 的棍子不能包含进来而仍保持对称性。

• 第五个样例：不能通过拼接（也不允许用多根棍子并联）得到符合条件的对称多边形。