You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

神秘矿石

题目背景

今天，传奇炼金术师艾肯又在炼金了。

题目描述

艾肯准备了某种神秘的矿石，这种矿石有 $n+1$ 种等级，分别为 $0,1,...,n-1,n$ 级。艾肯初始没有 $n$ 级的神秘矿石，对于其他等级 $0\le i\le n-1$ ，他有 $f_i$ 枚 $i$ 级矿石。这种矿石的炼制方式很神奇，炼制一枚 $i$ 级矿石需要 $0,1,...,i-1$ 级矿石各一枚和 $1$ 单位的魔力元素。注意：艾肯可以使用 $1$ 单位的魔力元素（从虚空中）炼制出一枚 $0$ 级矿石。

艾肯的目标是炼制出 $n$ 级的神秘矿石，这样他就可以把这个矿石卖给勇者换来大量的金钱。问他至少需要准备多少个单位的魔力元素。有多次询问。

输入格式

第一行一个整数 $t$ 表示数据组数。之后每两行描述一组数据： 每组数据的第一行一个整数 $n$，第二行 $n$ 个整数 $f_0,f_1,\ldots,f_{n-1}$ 。

输出格式

对于每组数据，输出一行一个整数，表示最少要消耗多少单位的魔力元素。

样例 #1

样例输入 #1

2
4
0 3 0 3
5
4 1 0 2 0

样例输出 #1

4
10

提示

样例解释 $1$

艾肯的目标是炼制一枚 $4$ 级矿石，他手里有 $1$ 级矿石和 $3$ 级矿石各 $3$ 枚，那么他可以这么操作：

1、从虚空炼制一枚 $0$ 级矿石。

2、消耗一枚 $0$ 级矿石和一枚 $1$ 级矿石炼制一枚 $2$ 级矿石。

3、再从虚空炼制一枚 $0$ 级矿石。

4、消耗一枚 $0$ 级矿石，一枚 $1$ 级矿石，一枚 $2$ 级矿石，一枚 $3$ 级矿石炼制一枚 $4$ 级矿石。

故总共消耗 $4$ 单位的魔力元素，可以证明不存在比这消耗更小的方案。

数据范围

对于全部数据，$1\le t\le 200$，$1\le n\le 50$，$0\le f_i\le 10^{16}$。

注意开long long。

• 子任务一（$5$ 分）：$n\le 2$。
• 子任务二（$17$ 分）：$n\le 20$。
• 子任务三（$7$ 分）：$f_i=0$。
• 子任务四（$9$ 分）：$f_i\le 1$。
• 子任务五（$20$ 分）：$f_i\le 2\times 10^3$。
• 子任务六（$9$ 分）：$f_0\le 10^{16}$ 且 $\forall j\ne 0,f_j=0$。
• 子任务七（$10$ 分）：$\exists i,f_i\le 10^{16}$ 且 $\forall j\ne i,f_j=0$。
• 子任务八（$23$ 分）：无特殊限制。