C. 染色游戏
每个测试点时间限制：2.5 秒
每个测试点内存限制：256 兆字节

Alice 和 Bob 正在玩一个游戏，游戏使用一个大小为 $n$ 的整数数组 $a$。

一开始，数组中的所有元素都是无色的。首先，Alice 选择 $3$ 个元素并将它们染成红色。然后 Bob 选择任意一个元素并将其染成蓝色（如果该元素原本是红色，则改为蓝色）。如果红色元素的和严格大于蓝色元素的值，则 Alice 获胜。

你的任务是计算 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 \dots \le a_n \le 10^5$）。

输入附加约束：所有测试用例的 $n$ 之和不超过 $5000$。

输出
对于每个测试用例，输出一个整数，表示 Alice 可以选择的 $3$ 个元素的方式数，使得她无论 Bob 如何操作都能获胜。

示例

输入

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

输出

0
0
10
2
16
0

说明

• 在前两个测试用例中，无论 Alice 选择哪三个元素，Bob 都能将某个元素染成蓝色，使 Alice 无法获胜。
• 在第三个测试用例中，Alice 可以选择任意三个元素。如果 Bob 将其中一个红色元素染成蓝色，红色元素的和为 $14$，蓝色元素值为 $7$；如果 Bob 选择一个无色元素，红色元素的和为 $21$，蓝色元素值为 $7$。
• 在第四个测试用例中，Alice 可以选择第 $1$、$3$、$4$ 个元素，或者第 $2$、$3$、$4$ 个元素。