将举办一场有 128 支队伍参加的锦标赛，队伍编号为 $1, 2, \dots, 128$。对于每对 $i < j$，队伍 $j$ 比队伍 $i$ 更强，在他们之间的比赛中，队伍 $j$ 总是获胜。对于每支队伍 $i$，该队拥有 $P_i$ 名支持者。没有任何两支队伍拥有共同的支持者。

锦标赛将进行 7 轮比赛。在每一轮中，队伍将被分成若干对，使得每支队伍恰好属于一对。每一对进行一场比赛，负者被淘汰，胜者进入下一轮（如果有）。 形式化地： 在第一轮中，128 支队伍将被分成 64 场比赛。因此，64 支队伍将被淘汰，其余队伍进入下一轮。 在第二轮中，来自第一轮的 64 支获胜队伍将被分成 32 场比赛。 在第三轮中，来自第二轮的 32 支获胜队伍将被分成 16 场比赛。 依此类推，直到决赛（第七轮），剩下的两支队伍进行一场比赛。

显然，越靠后的轮次价值越高。因此，第 $r$ 轮的门票价格为 $r$。在第 $r$ 轮中，队伍 $i$ 和队伍 $j$ 之间的比赛将产生 $r \cdot (P_i + P_j)$ 的收入，因为两支队伍的每一位支持者都会购买该场比赛的门票，每张门票价格为 $r$。

你负责安排所有轮次的对阵，你的目标是选择对阵方式，使得锦标赛产生的总收入最大化。求出这个最大总收入。

输入格式

• 输入的第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例包含一行输入，其中有 128 个整数 $P_1, P_2, \dots, P_{128}$。

输出格式

对于每个测试用例，输出一行，表示可能的最大总收入。

数据范围

• $1 \le T \le 5$
• $1 \le P_i \le 10^9$

样例

样例输入 1

2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

样例输出 1

494
30318

说明

样例输入 1 在本文档中被拆分为多行以适应页面显示。实际上，在测试中所有 128 个数字都在同一行上。

样例解释

测试用例 1：由于所有 $P_i = 1$，所有比赛的收入均为 $r \cdot 2$，其中 $r$ 是轮次编号。 第 1 轮：64 场比赛，收入 $64 \cdot 2 = 128$ 第 2 轮：32 场比赛，收入 $32 \cdot 4 = 128$ 第 3 轮：16 场比赛，收入 $16 \cdot 6 = 96$ 第 4 轮：8 场比赛，收入 $8 \cdot 8 = 64$ 第 5 轮：4 场比赛，收入 $4 \cdot 10 = 40$ 第 6 轮：2 场比赛，收入 $2 \cdot 12 = 24$ * 第 7 轮：1 场比赛，收入 $1 \cdot 14 = 14$

总收入为 $128 + 128 + 96 + 64 + 40 + 24 + 14 = 494$。