人们普遍认为 Bajtazar 是整个行政区里最吝啬的人。有许多例子可以支持这一说法，其中最不重要的一点是，他的庄园甚至连围栏都没有。然而，Bajtazar 最近在地下室里发现了 $n$ 块旧木板，于是他决定至少建造一段围栏。

他将木板一块叠在另一块上，使得它们的长度依次为 $a_1, \dots, a_n$。他拿起第一块木板，切下一段长度为 $b$ 的木片，并将其钉在围栏的最左侧。然后，他切下下一段长度为 $b$ 的木片，并将其钉在前一段的旁边。他继续这样做，直到手中剩下的木片长度为 $c$ ($1 \leqslant c \leqslant b$)。虽然这块木片看起来有点太短了，但他觉得如果浪费掉这么好的一块木板实在太可惜了……于是他也把这块木片加到了围栏上。接着，他从堆里拿起第二块木板，然后是下一块，并对每一块木板重复整个过程。

当工作完成后，Bajtazar 看着结果……并得出结论：使用那些较短的木片可能确实不是最好的主意。他想：“这看起来一点也不像一个统一的设计”，于是他决定把整个围栏漆成白色，至少给它一种统一感。然而，他突然想到，如果我只把每隔一块木板漆成白色，而把剩下的木板留成棕色，我就可以（大约）少用一半的油漆，而且围栏看起来仍然像是一个经过深思熟虑、连贯的结构！于是，他只给每隔一块木板涂上了颜色，从最左边的那块开始。

然而，到了晚上，一个可怕的想法击中了他：如果他选择了不同的 $b$ 值，所使用的油漆总量会不会更少？好吧，现在已经无济于事了，但这种不必要的浪费的想法让 Bajtazar 彻夜难眠——他需要知道如果他选择建造任何其他可能高度的围栏，他会用掉多少油漆。请帮他找到答案，这样他终于可以安稳地入睡了（或者睡不着，这取决于你的计算结果）。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \leqslant z \leqslant 5$)。接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \leqslant n \leqslant 1\,000\,000$)，即木板的数量。接下来是 $n$ 个整数 $a_i$ ($1 \leqslant a_i \leqslant 1\,000\,000, \sum a_i \leqslant 1\,000\,000$)，表示连续木板的长度。

输出格式

对于每个测试用例，输出 $M$ 行，其中 $M$ 是该测试用例中所有 $a_i$ 值的最大值。第 $i$ 行应包含一个整数 $f_i$：如果 Bajtazar 选择的围栏高度为 $b = i$，他需要涂成白色的木板总长度。

样例

样例输入 1

1
4
10 7 2 8

样例输出 1

14
13
15
13
15
16
21
23
24
12

说明

对于高度 $b = 4$，连续围栏木桩的高度为：4 4 2 4 3 2 4 4。Bajtazar 需要涂漆的总长度为 $4 + 2 + 3 + 4$，因此第 4 行的答案是 13。 对于高度 $b = 5$，连续围栏木桩的高度为：5 5 5 2 2 5 3。Bajtazar 需要涂漆的总长度为 $5 + 5 + 2 + 3$，因此第 5 行的答案是 15。