1475: 数矩形

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:97 Solved:22

Description

M有N根木棍,他要拿他们来拼成矩形(长方形和正方形),简单来说,他会从N根木棍中,选出4个序号不同的木棍来拼成矩形,这视作一个合法的方案。


换而言之,对于能组成矩形的四个木棍,我们记他们输入时的序号分别是i,j,k,l,当i<j<k<l时,视作一个合法的方案。详情见样例


现在想知道对于给定的N根木棍,M能有多少种合法方案。

Input

输入第一行包含一个整数T,表示数据组数。
接下来T组数据,每组数据两行输入分别是:
    第一行一个整数N,表示木棍数量
    第二行N个整数Ai,Ai表示第i根木棍的长度是多少。

Output

输出包含N行,每行代表每组数据的答案。

Sample Input Copy

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

Sample Output Copy

3
0

HINT

例如样例中第一组数据,M可以选择的方案有(用木棍序号表示):(1,2,3,4) (1,2,3,5) (2,3,4,5)
N <= 100000,0<Ai<10^9