cabinfever 是一个举世闻名的先知，以喜好饲养了各种体型的小树人著称，他还有一个特殊的爱好，就是寻宝。sd0061 小岛风景秀美，藏匿着数不尽的金银财宝，可是那里有一头名为 skywalkert 的巨龙，终年守护着宝库。
cabinfever 现在计划来前往 sd0061 小岛寻觅宝藏，可是要对付 skywalkert 可不是一件容易的事，他饲养的小树人又实在是太小了，会被轻易地焚烧殆尽，于是他想要获得一个更为强大的帮手。
神秘商人 ConnorZhong 有一种神奇的缝合机器，可以把多个小树人一起合并成一个更大的小树人，当使用这个机器后，一个更大的树人会出现，而作为原料的小树人会被消灭。一般的，如果一次性要合并 $k$ 个树人，那么对于 $k$ 个体型分别为 $b_1,b_2,\dots,b_k$ 的小树人，合并之后会产生一个体型为 $B=\sum_{i=1}^{k} b_i$ 的大树人，并产生 $B$ 的费用，每个新生成的树人和普通的树人本质上并没有什么区别，依旧可以被用作合并的材料。ConnorZhong 的缝合机器有一个额定功率 $P$，表示每一次合并操作最少需要 $2$ 个小树人，最多时原料可以是 $P$ 个树人，具体原料的多少可以任意选定，但是不能超过 $P$。
cabinfever 现在拥有 $N$ 个小树人，体型分别为 $a_1,a_2,\dots,a_N$，现在他要将所有的小树人都合并为一个小树人，使其体型为 $\sum_{i=1}^N a_i$。 由于缝合机器的功率限制，他可能需要多次合并操作。
每组数据请依次回答 $N-1$ 组询问，表示当 ConnorZhong 的缝合机器功率分别为 $2,3,4,\dots,N$ 时，cabinfever 的最小花费。
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
包含两行，第一行包含一个正整数 $N$。
第二行包含 $N$ 个非负整数 $a_i$。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。
保证所有的数据满足 $1 \leq T \leq 50, 2 \leq N \leq 2 \times 10^5, 0 \leq a_i \leq 10^6$。
保证 $80\%$ 的数据满足 $N \leq 2 \times 10^3$。
对于每组数据，输出一行，包含$N-1$ 整数，第 $i$ 个整数表示当 $P=i+1$ 时的最小花费。输出中在一行的每个数字之间用恰好一个空格隔开，不能有其他额外空格。
1
4
4 2 3 119 13 10