该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

C. 小聪的序列

小聪有一个序列 $a_1, \dots, a_n$，他不希望序列中的数差异太大。

小聪会根据 $a$ 序列计算出一个新的序列 $b$，定义为：

且 $b_1 = a_1$。

小聪想知道 $\sum_{i = 1}^n b_i$ 的值，你能帮帮他么？

输入格式

第一行是一个正整数 $T$，表示测试数据的组数。

接下来有 $T$ 行，每行表示一组测试数据。每行以一个正整数 $n$ 开始，然后是 $n$ 个非负整数 $a_i$。

输出格式

每组测试数据一行表示答案。

样例输入1

2
5 1 2 3 4 5
7 2 9 7 4 6 2 6

样例输出1

5
14

数据范围

对于 $20\%$ 的数据，有 $1 \leq n \leq 100$。

对于 $30\%$ 的数据，有 $1 \leq n \leq 10^3$。

对于 $50\%$ 的数据，有 $1 \leq n \leq 10^4$。

对于 $100\%$ 的数据，有 $1 \leq T \leq 10, 1 \leq n \leq 10^5, 0 \leq a_i \leq 65536$。