Background

Special for beginners, ^_^

Description

巨佬wzc 闲来无事，给了蒟蒻ccx 一个长度为 n 的序列 a，并且允许蒟蒻操作这个序列，巨佬 wzc定义，一次操作要选定一个i∈(1,n)，然后将序列中第 i 个数变成与它相邻的两个数的平均数（实数），即 a[i] = (a[i - 1] + a[i + 1] )/ 2; 在可以进行无限次任意位置的操作的情况下，能得到的序列最小总和是多少？

蒟蒻 ccx 想要将序列的总和变得最小，但是又不太会操作，也不敢在巨佬的面前吱声，于是只好偷偷在半夜趁着wzc熟睡的时候，悄悄登入后台，把测试数据改掉。 蒟蒻ccx将测试数据修改成，通过选择序里中相邻的两个数，就可以将这两个数的值都改成这两个数的平均值。可以进行无限次操作，只要在这种条件下得到该序列和的最小值，就可以通过测试数据，鱼目混珠，偷偷a题。 （巨巨wzc的规则被悄悄推翻了，现在只有通过蒟蒻ccx无敌弱化后的规则实现题目要求才可以a题，毕竟没有人知道ccx已经悄悄的改掉了后台的测试数据）

真是神清气爽的一天啊，走咯！临走前，蒟蒻ccx瞥了熟睡的一眼，当即会心一笑。静悄悄的走向wzc的床边，这个瓜楞，脚都伸到被子外面去啦！ccx无奈的摇了摇头，上前轻轻的替wzc将被子给盖好，苦笑着走到门旁，回头又看了看熟睡中的wzc，最后缓缓地将门带上。 满载一船星辉，在星辉斑斓里放歌。但我不能放歌，悄悄是别离的笙箫.夏虫也为我沉默，沉默是今晚的康桥！悄悄的我走了，正如我悄悄的来；我挥一挥衣袖，不带走一片云彩。

注：如果有a1 a2 a3, a4, a5 五个数字， 只能选取(a1, a2),(a2, a3),(a3, a4),(a4, a5)四种相邻的情况，不能选取(a1, a3)或者(a2, a5)这种不相邻的情况。

Format

Input

第一行给定一个整数t ∈[1,100]， 表示测试样例的组数; 接下来一行给出一个正整数n（n <= 10^6 ）， 代表序列的长度； 接下来一行给出n个整数ai， (-10^4 <= ai <= 10^4)；

Output

输出t行 每组样例在一行中输出一个整数，表示对序列进行操作后得到的序列总和的最小值。

Samples

2
1
100
2
-1 1

100
0

Tips

第二组样例解释： 选择a1 和a2， 使得a1 = a2 = (-1 + 1) / 2 = 0; 所以答案等于a1 + a2 = 0 + 0 = 0;