Count triangle

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一开始就出一大堆英文题确实不好,那么现在来一道中文题目(虽然我觉得英文比中文好解释清楚)。
题目是这样子的:给定N条边,编号从1~N,每条边都有一个边长,问可以组成多少个不同的三角形(有一条边的编号不同便视为不同的三角形)。
请机智的你来解决这道题吧~

Input

 输入数据的第一行为一个整数T(T <= 10),表示接下来数据的组数。
每组数据占两行:
第一行为一个正整数N(3 <= N <= 3000)。
第二行按照编号从1~N的顺序依次给出每条边的边长xi(1 <= xi <= 2^30),每个数之间用一个空格隔开。
 

Output

 输出一共T行,每行一个整数,表示可以组成的不同的三角形的个数。

Sample Input

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

Sample Output

7
10

Hint

 

Source

HDU shadow95