Alice 和 Bob 正在使用大小为 $$$n$$$ 的整数数组 $$$a$$$ 玩游戏。
最初,数组的所有元素都是无色的。首先,Alice 选择 $$$3$$$ 元素并将它们涂成红色。然后鲍勃选择任何元素并将其着色为蓝色(如果它是红色 - 重新着色)。如果红色元素的总和严格大于蓝色元素的值,则爱丽丝获胜。
你的任务是计算 Alice 可以选择 $$$3$$$ 元素以获胜的方式数量,无论 Bob 的行为如何。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \cdots \le a_n \le 10^5$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,打印一个整数 - 无论 Bob 的行为如何,Alice 都可以选择 $$$3$$$ 元素以获胜的方式数。
示例
输入复制
631 2 341 1 2 457 7 7 7 751 1 2 2 462 3 3 4 5 551 1 1 1 3
输出复制
0 0 10 2 16 0
注意
在前两个测试用例中,无论 Alice 选择哪三个元素,Bob 都能够将其中一个元素涂成蓝色,这样 Alice 就不会获胜。
在第三个测试用例中,Alice 可以选择任意三个元素。如果 Bob 对其中一个红色元素进行着色,则红色元素的总和将为 $$$14$$$,蓝色元素的总和将为 $$$7$$$。如果 Bob 选择无色元素,则红色元素的总和将为 $$$21$$$,蓝色元素的总和将为 $$$7$$$。
在第四个测试用例中,Alice 可以选择 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th 元素,或者 $$$2$$$-nd、$$$3$$$-rd 和 $$$4$$$-th 元素。