4135: qko 的树

众所周知 qko 非常擅长树 (数) 学，今天他沉迷于树 (数) 的海洋中，种了一棵二叉树。
这棵树上有许多果子 (叶子节点), 每个果子对应有美味值 W_i，深度 L_i，代价 c_i = L_i ∗ W_i。其中深度的定义如下：
在下图中，A 点的深度为 0 ，B 点的深度为 1，C, D 点的深度为 2 ，以此类推其他点的深度。


现在 qko 就凭借他超人的想象力构造了一颗代价 c_i 之和最小的树。qko 把这棵树的叶子节点按先序遍历的顺序拿出来去让 zxy 还原，然而 zxy 太菜了还原不了整棵树。于是 qko 放宽了要求，只让 zxy 输出原来树的代价就可以了，可是 zxy 还是不会。聪明的你能帮帮 zxy 吗？

第一行一个 T(T ≤ 5) 代表组数；
每组数据包含两行，其中第一行一个正整数 n(n ≤ 3500)，第二行包含 n 个整数，以空格分隔，第 i 个数字代表 W_i(W_i ≤ 10⁹) 。

1
6
1 2 3 4 5 6

51