题目描述

Dave 在玩一局游戏，他的面前有一排防御塔。

总共有 $n$ 个防御塔，防御塔从左到右排成了一排。第 $i$ 个防御塔的攻击力为 $a_i$。

Dave 一开始在 $1$ 号防御塔的位置。假设他当前在 $p$ 号防御塔的位置，他可以选择以下两种操作中的任意一种：

• 移动到 $p+1$ 号防御塔的位置（$p = n$ 时不允许进行此操作）；
• 不移动，但是选择一个下标 $i \le p$，将 $i$ 号防御塔摧毁。

每次操作结束后，未摧毁的所有防御塔都会对 Dave 造成一次攻击，造成的总伤害为未摧毁的防御塔的攻击力之和。

Dave 要摧毁所有的防御塔。他想知道最优操作下，最少会受到多少伤害。

输入格式

第一行一个正整数 $T$，表示游戏的局数。

接下来 $T$ 次询问，每次询问包含两行。

第一行一个正整数 $n$，代表防御塔的数量。

第二行 $n$ 个正整数 $a_i$，第 $i$ 个数代表防御塔 $i$ 的攻击力。

输出格式

共 $T$ 行，每行一个整数，表示该局游戏中，最优操作下最少会受到多少伤害。

3
3
3 2 1
2
1 3
1
5

8
5
0

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 8$；
• 对于 $60\%$ 的数据，$1 \le T \le 200$，$1 \le n \le 200$；
• 对于 $100\%$ 的数据，$1 \le T \le 5000$，$1 \le n, \sum n \le 5000$，$1 \le a_i \le 10^9$。