You are given an array $a_1, a_2 \dots a_n$. Calculate the number of tuples $(i, j, k, l)$ such that:   $1 \le i < j < k < l \le n$;  $a_i = a_k$ and $a_j = a_l$; 


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($4 \le n \le 3000$) — the size of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the array $a$.

It's guaranteed that the sum of $n$ in one test doesn't exceed $3000$.


-----Output-----

For each test case, print the number of described tuples.


-----Example-----
Input
2
5
2 2 2 2 2
6
1 3 3 1 2 3

Output
5
2



-----Note-----

In the first test case, for any four indices $i < j < k < l$ are valid, so the answer is the number of tuples.

In the second test case, there are $2$ valid tuples:   $(1, 2, 4, 6)$: $a_1 = a_4$ and $a_2 = a_6$;  $(1, 3, 4, 6)$: $a_1 = a_4$ and $a_3 = a_6$.

Difficulty: interview

Starter code:

Solutions:
class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

import sys,random

input=sys.stdin.readline

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    pair=[[] for i in range(n+1)]
    for i in range(n):
        for j in range(i+1,n):
            if a[i]==a[j]:
                pair[i+1].append(j+1)

    bit=BIT(n)
    ans=0
    for i in range(1,n+1):
        minus=bit.query(i)
        for r in pair[i]:
            ans+=bit.query(r-1)-minus
        for r in pair[i]:
            bit.update(r,1)

    print(ans)
    



from sys import stdin

tt = int(stdin.readline())

for loop in range(tt):

    n = int(stdin.readline())
    a = list(map(int,stdin.readline().split()))

    l = [0] * (n+1)
    ans = 0

    for j in range(n):
        r = [0] * (n+1)
        for k in range(n-1,j,-1):
            ans += l[a[k]] * r[a[j]]
            r[a[k]] += 1
        l[a[j]] += 1

    print (ans)
            
    


def calcCntAtPrefix(a):
    cntAtPrefix = [[0] * (len(a) + 1)]
    for i, x in enumerate(a):
        cntAtPrefix.append(cntAtPrefix[-1][:])
        cntAtPrefix[-1][x] += 1
    return cntAtPrefix

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    cntAtPrefix = calcCntAtPrefix(a)
    cntAtSuffix = calcCntAtPrefix(a[::-1])

    ans = 0
    for j in range(n):
        for k in range(j + 1, n):
            ans += cntAtPrefix[j][a[k]] * cntAtSuffix[n - 1 - k][a[j]]
    print(ans)

for t in range(int(input())):
    solve()


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    d = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] == a[j]:
                d[i][j] = 1
    for i in range(n):
        for j in range(n - 1):
            d[i][j + 1] += d[i][j]
    for i in range(n - 1):
        for j in range(n):
            d[i + 1][j] += d[i][j]
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] == a[j]:
                ans += d[j - 1][n - 1] - d[j - 1][j] - d[i][n - 1] + d[i][j]
    print(ans)

import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    n=II()
    aa=LI1()
    cnt=[0]*n
    ans=0
    for i,a in enumerate(aa):
        cur=0
        for a2 in aa[i+1:]:
            if a2==a:ans+=cur
            cur+=cnt[a2]
        cnt[a]+=1
    print(ans)