The weight of a sequence is defined as the number of unordered pairs of indexes $(i,j)$ (here $i \lt j$) with same value ($a_{i} = a_{j}$). For example, the weight of sequence $a = [1, 1, 2, 2, 1]$ is $4$. The set of unordered pairs of indexes with same value are $(1, 2)$, $(1, 5)$, $(2, 5)$, and $(3, 4)$.

You are given a sequence $a$ of $n$ integers. Print the sum of the weight of all subsegments of $a$.

A sequence $b$ is a subsegment of a sequence $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print a single integer — the sum of the weight of all subsegments of $a$.


-----Examples-----

Input
2
4
1 2 1 1
4
1 2 3 4
Output
6
0


-----Note-----

In test case $1$, all possible subsegments of sequence $[1, 2, 1, 1]$ having size more than $1$ are:

$[1, 2]$ having $0$ valid unordered pairs;

$[2, 1]$ having $0$ valid unordered pairs;

$[1, 1]$ having $1$ valid unordered pair;

$[1, 2, 1]$ having $1$ valid unordered pairs;

$[2, 1, 1]$ having $1$ valid unordered pair;

$[1, 2, 1, 1]$ having $3$ valid unordered pairs.

Answer is $6$.

In test case $2$, all elements of the sequence are distinct. So, there is no valid unordered pair with the same value for any subarray. Answer is $0$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

String algorithms

Implementation


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		arr[i] = [arr[i], i]
	arr.sort()
	if n == 1:
		print(0)
		continue
	cur = arr[-1][0]
	ind = n - arr[-1][1]
	su = 0
	for i in range(n - 2, -1, -1):
		if arr[i][0] != cur:
			cur = arr[i][0]
			ind = n - arr[i][1]
			continue
		su += (arr[i][1] + 1) * ind
		ind += n - arr[i][1]
	print(su)


import sys, math, bisect
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors
from collections import deque, defaultdict, Counter
import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	for i in range(n):
		if arr[i] in freq:
			freq[arr[i]].append(i + 1)
		else:
			freq[arr[i]] = [i + 1]
	ans = 0
	for x in freq:
		sz = len(freq[x])
		pre = [0] * sz
		pre[-1] = n - freq[x][-1] + 1
		for i in range(sz - 2, -1, -1):
			pre[i] = pre[i + 1] + (n - freq[x][i] + 1)
		for i in range(sz - 1):
			ans += freq[x][i] * pre[i + 1]
	print(ans)


import sys
input = sys.stdin.readline

def compress(init_val):
	t = sorted(set(init_val))
	d = dict([[t[i], i] for i in range(len(t))])
	res = [0] * len(init_val)
	for i in range(len(init_val)):
		res[i] = d[init_val[i]]
	return res
for _ in range(int(input())):
	n = int(input())
	a = compress(list(map(int, input().split())))
	table = [0] * n
	mx = max(a)
	s = [[] for _ in range(mx + 1)]
	for i in range(n):
		s[a[i]].append(i)
	for x in range(mx + 1):
		for t in range(len(s[x]) - 2, -1, -1):
			i = s[x][t]
			j = s[x][t + 1]
			table[j] += n - j
			table[i] += table[j]
		i = s[x][0]
		table[i] += n - i
	res = 0
	for i in range(n):
		l = i + 1
		r = max(0, table[i] - (n - i))
		res += l * r
	print(res)


from sys import stdin

def main():
	for _ in range(int(stdin.readline())):
		n = int(stdin.readline()) + 1
		(res, cnt) = (0, {})
		for (i, s) in enumerate(stdin.readline().split(), 1):
			res += (n - i) * cnt.setdefault(s, 0)
			cnt[s] += i
		print(res)
main()


def solve():
	n: int = int(input())
	arr = [int(num) for num in input().split(' ')]
	(count, ans) = ({}, 0)
	for i in range(len(arr)):
		ans += (n - i) * count.get(arr[i], 0)
		count[arr[i]] = count.get(arr[i], 0) + i + 1
	return ans

def main_fun():
	t = int(input())
	while t > 0:
		print(solve())
		t -= 1
main_fun()


tt = int(input())
for _ in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	(ans, tmp) = (0, 0)
	value = dict()
	for i in range(n):
		if a[i] in value:
			tmp += value[a[i]]
		else:
			value[a[i]] = 0
		value[a[i]] += i + 1
		ans += tmp
	print(ans)


for u in range(int(input())):
	n = int(input())
	x = [int(w) for w in input().split()]
	s = set(x)
	d = {}
	for i in s:
		d[i] = []
	for i in range(n):
		d[x[i]].append(i)
	ans = 0
	for j in d:
		l = d[j]
		z = []
		if len(l) >= 2:
			for i in range(len(l)):
				z.append(n - l[i])
			for i in range(len(l) - 2, -1, -1):
				z[i] += z[i + 1]
			for i in range(len(l) - 1):
				ans += (l[i] + 1) * z[i + 1]
	print(ans)


from collections import defaultdict, deque
from heapq import heappush, heappop
from math import inf
ri = lambda : map(int, input().split())

def solve():
	n = int(input())
	A = list(ri())
	indexes = defaultdict(list)
	for i in range(n):
		indexes[A[i]].append(i)
	ans = 0
	for val in indexes:
		pref = 0
		for i in indexes[val]:
			ans += pref * (n - i)
			pref += i + 1
	print(ans)
t = 1
t = int(input())
while t:
	t -= 1
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dicmap = {}
	for i in l:
		dicmap[i] = 0
	ans = 0
	for i in range(0, n):
		ans += dicmap[l[i]] * (n - i)
		dicmap[l[i]] += i + 1
	print(ans)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import sys
import string
import random
from typing import List
sys.setrecursionlimit(99999)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mp = collections.defaultdict(int)
	cnt = collections.defaultdict(int)
	ans = 0
	pre = 0
	for (i, c) in enumerate(arr):
		ans += mp[c] * (n - i)
		mp[c] += i + 1
		cnt[c] += 1
	print(ans)


import sys
input = sys.stdin.readline
from collections import *
a = int(input())
for i in range(a):
	s = int(input())
	z = list(map(int, input().split()))
	al = defaultdict(list)
	for i in range(len(z)):
		al[z[i]].append(i + 1)
	total = 0
	for i in al:
		ans = al[i]
		t = [0 for i in range(len(ans))]
		if len(ans) <= 1:
			continue
		for i in range(len(ans) - 1, -1, -1):
			if i == len(ans) - 1:
				continue
			else:
				t[i] = t[i + 1] + ans[i + 1] - 1
		for i in range(len(ans)):
			g1 = len(z) * (len(ans) - (i + 1)) - t[i]
			total += g1 * ans[i]
	print(total)


def getval(v, k):
	if len(v) == 1:
		return 0
	v.sort()
	curr = 0
	i = len(v) - 1
	j = 0
	while i >= 1:
		curr += v[j] * i * k
		i -= 1
		j += 1
	sqsum = 0
	for x in v:
		sqsum += x * x
	sum = 0
	for x in v:
		sum += x
	sumsq = sum * sum
	b = (sumsq - sqsum) // 2
	return curr - b
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	v = []
	for i in range(n):
		v.append((arr[i], i + 1))
	v.sort()
	v2 = []
	curr_num = v[0][0]
	curr_cnt = 0
	curr_v = []
	for i in range(n):
		if v[i][0] == curr_num:
			curr_cnt += 1
			curr_v.append(v[i][1])
		else:
			v2.append(curr_v)
			curr_cnt = 1
			curr_num = v[i][0]
			curr_v = [v[i][1]]
	v2.append(curr_v)
	ans = 0
	for vec in v2:
		ans += getval(vec, n + 1)
	print(ans)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	value = {}
	(fa, ca) = (0, 0)
	for i in range(n):
		if a[i] in value:
			ca += value[a[i]]
		else:
			value[a[i]] = 0
		value[a[i]] += i + 1
		fa += ca
	print(fa)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	data = list(map(int, sys.stdin.readline().split()))
	dp = [0] * (n + 1)
	temp = dict()
	for idx in range(1, n + 1):
		dp[idx] += dp[idx - 1]
		if data[idx - 1] in temp:
			dp[idx] += temp[data[idx - 1]]
		else:
			temp[data[idx - 1]] = 0
		temp[data[idx - 1]] += idx
	print(sum(dp))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	cnt = {}
	for i in range(n):
		if a[i] in cnt:
			ans += (n - i) * cnt[a[i]]
		if a[i] in cnt:
			cnt[a[i]] += i + 1
		else:
			cnt[a[i]] = i + 1
	print(ans)
	t -= 1


from collections import defaultdict
T = int(input())
for case in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[arr[i]].append(i)
	ans = 0
	for key in d.keys():
		if len(d[key]) > 1:
			m = len(d[key])
			prefix = [0]
			for i in range(m - 1, 0, -1):
				prefix.append(prefix[-1] + (n - 1 - d[key][i] + 1))
			for i in range(m - 1):
				ans += (d[key][i] + 1) * prefix[-1 + -i]
	print(ans)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	lis = [*map(int, stdin.readline().split())]
	cnt = 0
	dic = {}
	for i in range(n):
		val = lis[i]
		if lis[i] in dic:
			cnt += (n - i) * dic[val]
			dic[val] += i + 1
		else:
			dic[val] = i + 1
	print(cnt)


import sys
from math import *
inf = 10 ** 9
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = {}
	ans = 0
	s = set(a)
	for i in range(n - 1, -1, -1):
		h[a[i]] = 0
	for i in range(n):
		ans += h[a[i]] * (n - i)
		h[a[i]] += i + 1
	print(ans)


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	dic = defaultdict(list)
	for i in range(n):
		dic[arr[i]].append([i + 1, n - i])
	cnt = 0
	for key in dic:
		l = len(dic[key])
		if l <= 1:
			continue
		for i in range(l - 2, -1, -1):
			dic[key][i][1] += dic[key][i + 1][1]
		for i in range(l - 1):
			cnt += dic[key][i][0] * dic[key][i + 1][1]
	print(cnt)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	ans = 0
	d = defaultdict(int)
	l = li()
	for (i, ele) in enumerate(l):
		ans += d[ele] * (n - i)
		d[ele] += i + 1
	pr(ans)
for _ in range(inp()):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = {}
	dp = [0 for _ in range(n)]
	ans = 0
	for i in range(n):
		if a[i] not in cnt:
			cnt[a[i]] = 0
		if i > 0:
			dp[i] = dp[i - 1] + cnt[a[i]]
		cnt[a[i]] += i + 1
		ans += dp[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	lst = [int(i) for i in input().split()]
	dct = {}
	dp = [0] * n
	ans = 0
	for ind in range(n):
		value = lst[ind]
		contribution = ind + 1
		if ind != 0:
			dp[ind] = dp[ind - 1]
		if value in dct:
			dp[ind] += dct[value]
		ans += dp[ind]
		if value in dct:
			dct[value] += contribution
		else:
			dct[value] = contribution
	print(ans)


def func():
	ind = dict()
	ans = 0
	for i in range(n):
		if a[i] not in ind:
			ind[a[i]] = i + 1
		else:
			ans += ind[a[i]] * (n - i)
			ind[a[i]] += i + 1
	print(ans)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	func()


def formula(index, N, K):
	answer = N * (K * (K - 1) // 2)
	sm = 0
	square_sum = 0
	front = K - 1
	last = 0
	for alpha in index:
		sm += alpha
		square_sum += alpha * alpha
		answer += alpha * (front * N - last)
		front -= 1
		last += 1
	answer -= (sm * sm - square_sum) // 2
	return answer
for _ in range(int(input())):
	N = int(input())
	indexes = {}
	p = list(map(int, input().split()))
	for i in range(N):
		a = p[i]
		if a in indexes:
			indexes[a].append(i)
		else:
			indexes[a] = [i]
	ans = 0
	for it in indexes.values():
		if len(it) >= 2:
			ans += formula(it, N, len(it))
	print(ans)


for __ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(len(l)):
		d.setdefault(l[i], []).append(i)
	ans = 0
	n1 = n
	for i in d:
		n = len(d[i])
		p = d[i]
		l = 0
		for j in range(0, n - 1):
			l = l + (p[j] + 1)
			r = n1 - p[j + 1]
			ans += l * r
	print(ans)


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		if a[i] in d:
			d[a[i]].append(i + 1)
		else:
			d[a[i]] = [i + 1]
	ans = 0
	for i in d:
		vals = d[i][::-1]
		if len(vals) == 1:
			continue
		last = n - vals[0] + 1
		for j in vals[1:]:
			ans += j * last
			last += n - j + 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[l[i]] = 0
	ans = 0
	for i in range(n):
		ans += d[l[i]] * (n - i)
		d[l[i]] += i + 1
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	h = {}
	count = 0
	for i in range(len(lis)):
		if lis[i] not in h:
			h[lis[i]] = i + 1
		else:
			count += (n - i) * h[lis[i]]
			h[lis[i]] += i + 1
	print(count)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	count = 0
	for (i, c) in enumerate(a):
		prev = d.get(c, 0)
		count += prev * (n - i)
		d[c] = prev + i + 1
	print(count)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	d = dict()
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = [i]
		else:
			d[s[i]].append(i)
	res = 0
	for x1 in d:
		ln = len(d[x1])
		x = d[x1]
		pr = [x[0]]
		for i in range(1, ln):
			pr.append(pr[-1] + x[i])
		for i in range(ln - 1):
			first = x[i] + 1
			sm = (ln - i - 1) * n - (pr[-1] - pr[i])
			res += first * sm
	print(res)


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


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	ans = 0
	for i in range(n):
		ans += (n - i) * d[l[i]]
		d[l[i]] += i + 1
	print(ans)


totCases = int(input())
for _ in range(totCases):
	ans = 0
	(n, val) = (int(input()), input().split(' '))
	cnt = dict()
	for i in range(n):
		it = val[i]
		try:
			ans += cnt[it] * (n - i)
		except:
			cnt[it] = 0
		finally:
			cnt[it] += i + 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dict = {}
	ans = 0
	for (idx, val) in enumerate(a):
		if val not in dict:
			dict[val] = idx + 1
		else:
			ans += dict[val] * (n - idx)
			dict[val] += idx + 1
	print(ans)


def fun(n, ls):
	dp = [0 for i in range(n)]
	dct = {i: 0 for i in ls}
	ans = 0
	for i in range(n):
		if i > 0:
			dp[i] = dp[i - 1]
		if ls[i] in dct.keys():
			dp[i] += dct.get(ls[i])
		dct[ls[i]] = dct[ls[i]] + i + 1
		ans += dp[i]
	print(ans)
T = int(input())
for i in range(T):
	n = int(input())
	ls = list(map(int, input().split()))
	fun(n, ls)


for _ in range(int(input())):
	n = int(input())
	b = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		if b[i] not in d:
			d[b[i]] = []
		d[b[i]].append(i)
	ans = 0
	for j in d.values():
		z = []
		if len(j) > 1:
			for i in range(len(j)):
				z.append(n - j[i])
			for i in range(len(j) - 2, -1, -1):
				z[i] += z[i + 1]
			for i in range(len(j) - 1):
				ans += (j[i] + 1) * z[i + 1]
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	q = {}
	s = 0
	for i in range(n):
		if a[i] not in q:
			q[a[i]] = 0
		s += q[a[i]] * (n - i)
		q[a[i]] += i + 1
	print(s)


def read():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		solve(n, a)

def solve(n, a):
	ans = 0
	d = dict()
	for i in range(n):
		x = a[i]
		if x in d:
			ans += (n - i) * d[x]
			d[x] += i + 1
		else:
			d[x] = i + 1
	print(ans)
read()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = [i]
		else:
			d[a[i]].append(i)
	ans = 0
	for el in d:
		if len(d[el]) > 1:
			sp = [n - d[el][-1]]
			for i in range(2, len(d[el])):
				sp.append(sp[-1] + (n - d[el][-i]))
			for i in range(len(d[el]) - 1):
				ans += sp[-(i + 1)] * (d[el][i] + 1)
	print(ans)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil, log2, gcd
from bisect import bisect_right
from _collections import deque
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[a[i]] = d.get(a[i], [])
		d[a[i]].append(i)
	ans = 0
	for i in d:
		z = len(d[i])
		t = sum(d[i])
		for j in range(z):
			t -= d[i][j]
			ans += (d[i][j] + 1) * ((z - j - 1) * n - t)
	print(ans)


import sys
from collections import Counter
import math
num_cases = int(sys.stdin.readline().strip())
for case in range(1, num_cases + 1):
	N = int(sys.stdin.readline().strip())
	A = sys.stdin.readline().strip().split(' ')
	A = list(map(lambda x: int(x), A))
	len_A = len(A)
	count = 0
	info_dict = dict()
	for i in range(len_A):
		value = A[i]
		value2 = info_dict.get(value, 0)
		count += value2 * (len_A - i)
		info_dict[value] = value2 + i + 1
	print(count)


from typing import List

def solve(n: int, a: List[int]) -> int:
	count = {}
	for i in range(n):
		if a[i] in count:
			count[a[i]].append(i + 1)
		else:
			count[a[i]] = [i + 1]
	ans = 0
	for key in count:
		prefix_sum = 0
		for x in count[key]:
			ans += prefix_sum * (n - x + 1)
			prefix_sum += x
	return ans
test_cases = int(input())
for _ in range(test_cases):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))


import sys, os, io
import math, bisect, operator, itertools
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(test,) = Neo()
for _ in range(test):
	(n,) = Neo()
	A = Neo()
	d = defaultdict(int)
	(Ans, c) = (0, 0)
	for (ii, i) in enumerate(A):
		c += d[i]
		d[i] += 1 + ii
		Ans += c
	print(Ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = []
	for tmp in input().split():
		tmp = int(tmp)
		arr.append((tmp, len(arr)))
	arr = list(sorted(arr))
	cur_l = 0
	ans = 0
	while cur_l <= len(arr) - 2:
		cur_r = cur_l + 1
		while cur_r < len(arr) and arr[cur_r][0] == arr[cur_l][0]:
			cur_r += 1
		cur_r -= 1
		if cur_r == cur_l:
			pass
		else:
			tsum = 0
			for cur in reversed(range(cur_l, cur_r)):
				tsum += n - arr[cur + 1][1]
				ans += (arr[cur][1] + 1) * tsum
		cur_l = cur_r + 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	li = [int(x) for x in input().split()]
	di = {i: 0 for i in li}
	ans = 0
	for (i, j) in enumerate(li):
		ans += di[j] * (n - i)
		di[j] += i + 1
	print(ans)


from collections import defaultdict
from sys import stdin
input = stdin.readline

def solve():
	n = int(input())
	(dct, ans) = (defaultdict(list), 0)
	for (ind, el) in enumerate(input().split()):
		dct[int(el)].append(ind)
	for i in dct:
		pf = 0
		for j in dct[i]:
			ans += pf * (n - j)
			pf += j + 1
	print(ans)
for test in range(int(input())):
	solve()


from collections import defaultdict

def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	dp = [0] * (n + 1)
	d = defaultdict(int)
	for (i, a) in enumerate(arr, start=1):
		dp[i] += dp[i - 1]
		dp[i] += d[a]
		d[a] += i
	return sum(dp)
for _ in range(int(input().strip())):
	print(solve())


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
sys.setrecursionlimit(10000000)
for _ in range(I()):
	n = I()
	a = L()
	dp = [0] * n
	d = {}
	d[a[0]] = 1
	for i in range(1, n):
		dp[i] = dp[i - 1] + d.get(a[i], 0)
		d[a[i]] = d.get(a[i], 0) + i + 1
	print(sum(dp))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = 0
	resm = 0
	val = {}
	for j in range(n):
		if a[j] in val:
			resm += val[a[j]]
		else:
			val[a[j]] = 0
		val[a[j]] += j + 1
		res += resm
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	tmp = list(set(a))
	for e in tmp:
		d[e] = []
	for j in range(n):
		d[a[j]].append(j + 1)
	ans = 0
	for key in d:
		qw = len(d[key])
		if qw > 1:
			pref_sum = [d[key][0]]
			for j in range(1, qw):
				pref_sum.append(pref_sum[-1] + d[key][j])
				ans += pref_sum[j - 1] * (n - d[key][j] + 1)
	print(ans)


def process(x):
	s = 0
	d = {}
	for i in range(len(x)):
		if x[i] in d:
			s += (len(x) - i) * d[x[i]]
			d[x[i]] += i + 1
		else:
			d[x[i]] = i + 1
	print(s)
n = int(input())
for i in range(n):
	l = int(input())
	x = [int(p) for p in list(input().split(' '))]
	process(x)


import os, sys, time, collections as c, math, pprint as p, itertools as it, operator as op, bisect as bs, functools as fn
(maxx, localsys, mod) = (float('inf'), 0, int(1000000000.0 + 7))
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)
ceil = lambda n, x: (n + x - 1) // x
(osi, oso) = ('/home/priyanshu/Documents/sublimetextproject/input.txt', '/home/priyanshu/Documents/sublimetextproject/output.txt')
if os.path.exists(osi):
	sys.stdin = open(osi, 'r')
	sys.stdout = open(oso, 'w')
input = sys.stdin.readline

def maps():
	return map(int, input().split())

def dprint(*args):
	[print(i) for i in args]
for _ in range(int(input())):
	n = int(input())
	a = list(maps())
	(fa, ca, d) = (0, 0, c.defaultdict(int))
	for i in range(n):
		ca += d[a[i]]
		d[a[i]] += i + 1
		fa += ca
	print(fa)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	a = [0]
	b = [int(i) for i in input().split()]
	a = a + b
	d = defaultdict(lambda : 0)
	ans = 0
	for i in range(1, n + 1):
		ans += d[a[i]] * (n - i + 1)
		d[a[i]] += i
	print(ans)


import sys
import math
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	line = []
	line = [int(i) for i in sys.stdin.readline().split()]
	cum_ind = {}
	ans = 0
	for (i, v) in enumerate(line):
		if v not in cum_ind.keys():
			cum_ind[v] = 0
		ans += cum_ind[v] * (n - i)
		cum_ind[v] += i + 1
	print(ans)


import sys
import math

def answer(n, a):
	d = dict()
	dp = [0 for _ in range(n + 1)]
	for i in range(n):
		dp[i + 1] = dp[i]
		if a[i] not in d:
			d[a[i]] = i + 1
		else:
			dp[i + 1] += d[a[i]]
			d[a[i]] += i + 1
	return sum(dp)

def main():
	t = int(sys.stdin.readline())
	while t:
		n = int(sys.stdin.readline())
		a = tuple(map(int, sys.stdin.readline().split()))
		print(answer(n, a))
		t -= 1
	return
main()


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


def cal(n, ind_list):
	ind1_list = [ind + 1 for ind in ind_list]
	red_list = [n - ind for ind in ind_list]
	pre_sum = [0]
	for ind1 in ind1_list:
		pre_sum.append(pre_sum[-1] + ind1)
	res = 0
	for i in range(1, len(red_list)):
		res += red_list[i] * pre_sum[i]
	return res

def getResult(n, a_list):
	v_dict = {}
	for i in range(n):
		v = a_list[i]
		if v in v_dict:
			v_dict[v].append(i)
		else:
			v_dict[v] = [i]
	res = 0
	for v in v_dict.keys():
		if len(v_dict[v]) >= 2:
			res += cal(n, v_dict[v])
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a_list = [int(k) for k in input().split()]
	print(getResult(n, a_list))


def main():
	T = int(input())
	for c in range(1, T + 1):
		n = int(input())
		arr = input().rstrip().split(' ')
		for i in range(n):
			arr[i] = int(arr[i])
		d = {}
		ans = 0
		for i in range(n):
			l = i + 1
			r = n - i
			if arr[i] not in d:
				d[arr[i]] = l
			else:
				ans += d[arr[i]] * r
				d[arr[i]] += l
		print(ans)
main()


import sys
from math import *
test = int(input())
while test:
	test -= 1
	n = int(input())
	a = list(map(int, input().split()))
	value = {}
	(res, ans) = (0, 0)
	for i in range(n):
		if a[i] in value:
			ans += value[a[i]]
		else:
			value[a[i]] = 0
		value[a[i]] += i + 1
		res += ans
	print(res)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	idx = {}
	for i in range(n):
		idx[a[i]] = []
	for i in range(n):
		idx[a[i]].append(i)
	ans = 0
	for x in idx:
		S = 0
		for i in idx[x]:
			ans += S * (n - i)
			S += i + 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	f = defaultdict(int)
	c = 0
	for i in range(n - 1, -1, -1):
		c += (i + 1) * f[l[i]]
		f[l[i]] += n - i
	print(c)


from collections import defaultdict
for i in range(int(input())):
	ans = 0
	n = int(input())
	d = defaultdict(lambda : 0)
	a = list(map(int, input().split()))
	for j in range(n):
		ans += d[a[j]] * (n - j)
		d[a[j]] += j + 1
	print(ans)


from collections import defaultdict

def compute_prefix(iterable):
	ret = []
	for val in iterable:
		ret.append(ret[-1] + val if ret else val)
	return ret

def solve():
	positions1 = defaultdict(list)
	positions2 = defaultdict(list)
	n = int(input())
	arr = [int(x) for x in input().split()]
	vals = set()
	for (idx, val) in enumerate(arr):
		positions1[val].append(idx)
		positions2[val].append(n - idx)
		vals.add(val)
	ans = 0
	for val in vals:
		prefix = compute_prefix(positions2[val])
		for (idx, l) in enumerate(positions1[val]):
			ans += (l + 1) * (prefix[-1] - prefix[idx])
	return ans
T = int(input())
for _ in range(T):
	print(solve())


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	v = {}
	(f, c) = (0, 0)
	for i in range(n):
		if l[i] in v:
			c += v[l[i]]
		else:
			v[l[i]] = 0
		v[l[i]] += i + 1
		f += c
	print(f)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(ans, c) = (0, 0)
	d = {}
	for i in range(n):
		if a[i] in d:
			c += d[a[i]]
			d[a[i]] += i + 1
		else:
			d[a[i]] = i + 1
		ans += c
	print(ans)


def solve(n, a):
	b = {}
	for i in range(n):
		if not a[i] in b:
			b[a[i]] = []
		b[a[i]].append(i + 1)
	m = n + 1
	c = 0
	for (x, d) in b.items():
		k = 0
		for i in range(len(d)):
			if i > 0:
				c += k * (m - d[i])
			k += d[i]
	return c
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))


from sys import stdin, stdout
from collections import deque
import bisect
import math
R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))
output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))
T = int(input())
for _ in range(T):
	n = int(input())
	l = RL(int)
	dic = dict()
	for i in range(n):
		if l[i] not in dic.keys():
			dic[l[i]] = [i]
		else:
			dic[l[i]].append(i)
	ans = 0
	for val in dic.values():
		suf = [0] * len(val)
		suf[-1] = n - val[-1]
		for i in range(1, len(val)):
			suf[len(val) - i - 1] = suf[len(val) - i] + n - val[len(val) - 1 - i]
		for i in range(len(val) - 1):
			ans += (val[i] + 1) * suf[i + 1]
	print(ans)


import sys, heapq
from collections import defaultdict, deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	G = defaultdict(list)
	for i in range(n):
		G[A[i]].append(i)
	ans = 0
	for ele in G:
		arr = G[ele]
		m = len(arr)
		bef = 0
		for i in range(m):
			v = arr[i]
			ans = ans + (n - v) * bef
			bef = bef + v + 1
	print(ans)


from sys import stdin, stdout
input = stdin.readline

def im():
	return map(int, input().split())

def ii():
	return int(input())

def il():
	return list(map(int, input().split()))

def ins():
	return input()[:-1]
for _ in range(ii()):
	n = ii()
	lis = il()
	dic = {}
	ans = 0
	for i in range(n):
		if lis[i] not in dic:
			dic[lis[i]] = i + 1
		else:
			ans += dic[lis[i]] * (n - i)
			dic[lis[i]] += i + 1
	print(ans)


for ttt in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = [i + 1]
		else:
			d[arr[i]].append(i + 1)
	ans = 0
	for i in d:
		psum = 0
		for item in d[i]:
			ans += psum * (n - item + 1)
			psum += item
	print(ans)


from sys import stdin
input = stdin.readline

def answer():
	d = dict()
	for i in range(n):
		try:
			d[a[i]].append(i)
		except:
			d[a[i]] = [i]
	ans = 0
	for i in d.keys():
		value = 0
		for j in range(len(d[i])):
			ans += value * (n - d[i][j])
			value += d[i][j] + 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	ps = {}
	ans = 0
	for i in range(n):
		if arr[i] not in ps:
			ps[arr[i]] = [i + 1]
		else:
			ans += ps[arr[i]][-1] * (n - i)
			ps[arr[i]].append(ps[arr[i]][-1] + i + 1)
	return ans
for _ in range(int(input())):
	print(solve())


def mapit():
	temp = list(map(int, input().split()))
	return temp
from math import log2

def solution():
	n = int(input())
	arr = mapit()
	dp = [0] * n
	ans = 0
	dicty = {}
	for i in range(n):
		if i > 0:
			dp[i] = dp[i - 1]
		if arr[i] in dicty:
			dp[i] += dicty[arr[i]]
			dicty[arr[i]] += i + 1
		else:
			dicty[arr[i]] = i + 1
		ans += dp[i]
	print(ans)
	return
t = int(input())
while t:
	t -= 1
	solution()


for step in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	top = 0
	hash = {}
	dp = [0] * (n + 1)
	for i in range(n):
		if i > 0:
			dp[i] = dp[i - 1]
		if a[i] in hash.keys():
			dp[i] += hash[a[i]]
		else:
			hash[a[i]] = 0
		hash[a[i]] += i + 1
		top += dp[i]
	print(top)


def readArr():
	return [int(x) for x in input().split()]

def solve():
	N = int(input())
	d = {}
	arr = readArr()
	for i in range(N):
		a = arr[i]
		if d.get(a, False):
			d[a].append([i + 1, N - i])
		else:
			d[a] = []
			d[a].append([i + 1, N - i])
	ans = 0
	for k in d.keys():
		ln = len(d[k])
		ls = 0
		for i in range(ln):
			ans += ls * d[k][i][1]
			ls += d[k][i][0]
	print(ans)
T = int(input())
for t in range(T):
	solve()


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
MOD = 10 ** 9 + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter

def main():
	for _ in range(int(input())):
		n = int(input())
		a = [*map(int, input().split())]
		s = 0
		cnt = Counter()
		for (i, ai) in reversed(list(enumerate(a))):
			s += cnt[ai] * (i + 1)
			cnt[ai] += n - i
		print(s)
main()


import math
import sys
from collections import deque, Counter, OrderedDict, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
mx = 10 ** 9 + 7
for _ in range(inp()):
	n = inp()
	l = inlt()
	d = defaultdict(lambda : [])
	for i in range(n):
		d[l[i]].append(i + 1)
	ans = 0
	for each in d:
		v = d[each]
		a = v[0]
		for i in range(1, len(v)):
			ans += a * (n - v[i] + 1)
			a += v[i]
	print(ans)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	l = [*map(int, sys.stdin.readline().split())]
	a = 0
	p = {x: 0 for x in l}
	for i in range(n):
		a += p[l[i]] * (n - i)
		p[l[i]] += i + 1
	sys.stdout.write(str(a) + '\n')


from sys import stdin, stdout
import math
import heapq
R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))
output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))
for tc in range(int(R())):
	n = int(R())
	a = RL(int)
	d = dict()
	ans = [0]
	for (i, x) in enumerate(a):
		if x in d:
			ans.append(d[x] + ans[-1])
			d[x] += i + 1
		else:
			ans.append(ans[-1])
			d[x] = i + 1
	print(sum(ans))


n = int(input())
test_case = list()
for i in range(n):
	k = int(input())
	s = input()
	a = list(map(int, s.split()))
	test_case.append((k, a))
for (k, array) in test_case:
	group_index_by_value = dict()
	count = 0
	for (i, v) in enumerate(array):
		if v in group_index_by_value:
			count += (k - i) * group_index_by_value[v]
			group_index_by_value[v] += i + 1
		else:
			group_index_by_value[v] = i + 1
	print(count)


from __future__ import print_function
from collections import *
from sys import stdin
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()
for _ in range(t):
	(n,) = gil()
	a = gil()
	idx = {}
	i = -1
	for v in a:
		i += 1
		if v not in idx:
			idx[v] = []
		idx[v].append(i)
	ans = 0
	for v in idx:
		sm = 0
		l = idx[v]
		if len(l) == 1:
			continue
		for j in reversed(range(len(l) - 1)):
			sm += n - l[j + 1]
			ans += (l[j] + 1) * sm
	print(ans)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
from collections import deque
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		d = collections.defaultdict(lambda : 0)
		dp = [0] * n
		s = set()
		ans = 0
		for j in range(n):
			if j > 0:
				dp[j] = dp[j - 1]
			if a[j] not in s:
				s.add(a[j])
			else:
				dp[j] += d[a[j]]
			ans += dp[j]
			d[a[j]] += j + 1
		print(ans)
main()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	hashTable = defaultdict(list)
	ans = 0
	for (idx, val) in enumerate(array, 1):
		hashTable[val].append(idx)
	for i in hashTable:
		prefixSum = 0
		for j in hashTable[i]:
			ans += prefixSum * (n - j + 1)
			prefixSum += j
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split()
	m = dict()
	ans = 0
	for (pos, elem) in enumerate(a):
		if elem not in m:
			m[elem] = 0
		ans += m[elem] * (n - pos)
		m[elem] += pos + 1
	print(ans)


t = int(input())
for _i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	ans = 0
	for i in reversed(range(n)):
		target = arr[i]
		if target in d:
			ans += (i + 1) * d[target]
			d[target] += n - i
		else:
			d[target] = n - i
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	pos = {}
	a = list(map(int, input().split(' ')))
	for (i, val) in enumerate(a):
		if val not in pos.keys():
			pos[val] = []
		pos[val].append(i)
	sum = 0
	for (_, l) in pos.items():
		past = 0
		for x in l:
			sum += (n - x) * past
			past += x + 1
	print(sum)


from sys import stdin, stdout
from collections import defaultdict
from itertools import accumulate
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	n = nmbr()
	a = lst()
	g = defaultdict(list)
	for i in range(n):
		g[a[i]] += [i]
	ans = 0
	for (k, l) in g.items():
		ps = list(accumulate(l))
		c = 1
		nn = len(ps)
		for i in range(nn - 1):
			ans += (l[i] + 1) * ((nn - c) * n - ps[-1] + ps[i])
			c += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = dict()
	res = 0
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = 0
		res += d[a[i]] * (n - i)
		d[a[i]] += i + 1
	print(res)


import bisect
from collections import defaultdict, Counter

def com(a, n):
	m = len(a)
	ans = 0
	cum_sum = [0]
	c = 0
	for x in a:
		c += x
		cum_sum.append(c)
	for i in range(0, m):
		ctr = m - i - 1
		sum_j = cum_sum[m] - cum_sum[i + 1]
		add = a[i] * ctr
		add += ctr * n - sum_j
		add += a[i] * ctr * (n - 1)
		add -= a[i] * sum_j
		ans += add
	return int(ans)

def main(a):
	n = len(a)
	idx_map = defaultdict(list)
	for (i, x) in enumerate(a):
		idx_map[x].append(i)
	ans = 0
	for l in idx_map.values():
		m = len(l)
		if m > 1:
			ans += com(list(l), n)
	return int(ans)
t = int(input())
outputs = []
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	output = main(arr)
	outputs.append(output)
for o in outputs:
	print(o)


from collections import defaultdict
import sys
input = sys.stdin.readline

def solve(n, a):
	ctr = defaultdict(int)
	ans = 0
	for i in range(n):
		ans += (n - i) * ctr[a[i]]
		ctr[a[i]] += i + 1
	print(ans)
	return
for nt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	solve(n, a)


for _ in range(int(input())):
	n = int(input())
	t = n
	s = list(map(int, input().split()))
	D = dict()
	for i in range(n):
		c = s[i]
		if c in D:
			D[c].append(i)
		else:
			D[c] = [i]
	ans = 0
	for I in D.values():
		if len(I) > 1:
			end = sum((t - I[i] for i in range(1, len(I))))
			for i in range(len(I) - 1):
				ans += (I[i] + 1) * end
				end -= t - I[i + 1]
	print(ans)


T = int(input())
for ti in range(T):
	N = int(input())
	array = input().split(' ')
	dic = {}
	prefix = [0 for i in range(N)]
	count = 0
	for i in range(N):
		array[i] = int(array[i])
		if i > 0:
			prefix[i] = prefix[i - 1]
		if array[i] in dic:
			prefix[i] += dic[array[i]]
			dic[array[i]] += i + 1
		else:
			dic[array[i]] = i + 1
		count += prefix[i]
	print(count)


from collections import defaultdict
T = int(input())
for t in range(T):
	n = int(input())
	xs = [int(x) for x in input().split()]
	nums = defaultdict(list)
	for (i, x) in enumerate(xs):
		nums[x].append(i)
	ans = 0
	for num in nums:
		subweight = 0
		for i in nums[num]:
			ans += (n - i) * subweight
			subweight += i + 1
	print(ans)


import itertools
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	C = defaultdict(int)
	for i in range(n):
		ans += C[a[i]] * (n - i)
		C[a[i]] += i + 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
import math
from queue import Queue
import collections
import itertools
import bisect
import heapq
import random

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	i = 2
	while i * i <= n:
		if primes[i] == True:
			for j in range(i * i, n + 1, i):
				primes[j] = False
		i += 1
	pr = []
	for i in range(0, n + 1):
		if primes[i]:
			pr.append(i)
	return pr

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sod(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s
for xyz in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		d[i] = []
	for i in range(0, n):
		d[l[i]].append(i)
	ans = 0
	for i in d:
		t = d[i].copy()
		for ii in range(1, len(t)):
			t[ii] += t[ii - 1]
		for ii in range(0, len(t)):
			ans += (n * (len(t) - ii - 1) - (t[-1] - t[ii])) * (d[i][ii] + 1)
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	d = defaultdict(int)
	ans = 0
	for i in range(n):
		ans += d[l[i]] * (n - i)
		d[l[i]] += i + 1
	print(ans)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
from collections import OrderedDict
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [*map(int, input().split())]
	h1 = OrderedDict()
	for i in range(n):
		x = a[i]
		if x in h1:
			h1[x].append(i)
		else:
			h1[x] = [i]
	h2 = h1.copy()
	for key in h2:
		ar = h2[key].copy()
		m = len(ar)
		ar.append(0)
		for i in reversed(range(m)):
			ar[i] = n - ar[i] + ar[i + 1]
		h2[key] = ar
	res = 0
	for key in h1:
		suf = h2[key]
		ar = h1[key]
		m = len(ar)
		for i in range(m):
			x = ar[i] + 1
			y = suf[i + 1]
			res += int(x) * int(y)
	print(str(res))
	print('\n')


from functools import reduce
import os
import sys
from collections import *
from decimal import *
from math import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def arr():
	return [int(i) for i in input().split()]

def sarr():
	return [str(i) for i in input()]

def starr():
	return [str(x) for x in input().split()]

def inn():
	return int(input())

def svalue():
	return tuple(map(str, input().split()))

def parr():
	return [value() for i in range(n)]

def Ceil(a, b):
	return a // b + int(a % b > 0)
albhabet = 'abcdefghijklmnopqrstuvwxyz'
mo = 1000000007
inf = 1e+18
div = 998244353
for _ in range(inn()):
	n = inn()
	a = arr()
	d = defaultdict(int)
	ans = 0
	sm = 0
	for i in range(n):
		if d[a[i]] != 0:
			sm += d[a[i]]
		d[a[i]] += i + 1
		ans += sm
	print(ans)


t = int(input())

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	lookup = {}
	ans = 0
	for i in range(n):
		a = A[i]
		if a not in lookup:
			lookup[a] = 0
		ans += lookup[a] * (n - i)
		lookup[a] += i + 1
	return ans
while t:
	t -= 1
	ans = solve()
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	hash = {}
	ans = 0
	cnt = 0
	for i in range(n):
		if a[i] in hash:
			cnt += hash[a[i]]
		else:
			hash[a[i]] = 0
		hash[a[i]] += i + 1
		ans += cnt
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	dp = [0] * (n + 1)
	d = dict()
	ans = 0
	for i in range(n):
		dp[i + 1] += dp[i]
		d.setdefault(a[i], 0)
		dp[i + 1] += d[a[i]]
		d[a[i]] += i + 1
		ans += dp[i + 1]
	print(ans)


import os
import sys
from math import *
from collections import *
from heapq import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcde'
M = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def INT():
	return int(input())

def STR():
	return input()

def INTs():
	return tuple(map(int, input().split()))

def ARRINT():
	return [int(i) for i in input().split()]

def ARRSTR():
	return [i for i in input().split()]
import collections

def solve(arr):
	memo = {}
	res = 0
	for (idx, cha) in enumerate(arr):
		if cha in memo:
			res += memo[cha] * (len(arr) - idx)
		else:
			memo[cha] = 0
		memo[cha] += idx + 1
	print(res)
for _ in range(INT()):
	_ = INT()
	solve(ARRINT())


from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
from sys import stdin
input = stdin.readline
mp = lambda : map(int, input().split())
it = lambda : int(input())
ls = lambda : list(input().strip().split())
mt = lambda r: [ls() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def fibo_n(n):
	return ((1 + sqrt(5)) / 2) ** n / sqrt(5)
for i in range(it()):
	a = it()
	b = list(mp())
	d = dd(lambda : 0)
	dp = [0] * a
	d[b[0]] += 1
	out = 0
	for i in range(1, a):
		dp[i] = dp[i - 1] + d[b[i]]
		d[b[i]] += i + 1
		out += dp[i]
	print(out)


import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0 for i in range(n + 1)]
	store = {}
	for i in range(1, n + 1):
		dp[i] = dp[i - 1]
		if a[i - 1] in store:
			dp[i] += store[a[i - 1]]
		else:
			store[a[i - 1]] = 0
		store[a[i - 1]] += i
	print(sum(dp))


for s in [*open(0)][2::2]:
	l = [*map(int, s.split())]
	a = 0
	n = len(l)
	p = {x: 0 for x in l}
	for i in range(n):
		a += p[l[i]] * (n - i)
		p[l[i]] += i + 1
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(d) for d in input().split()]
	d = {}
	for i in range(len(a)):
		if a[i] in d:
			d[a[i]].append(i + 1)
		else:
			d[a[i]] = [i + 1]
	c = 0
	for i in d:
		if len(d[i]) > 1:
			s1 = 0
			s2 = 0
			sq = 0
			sum_ = 0
			for j in range(len(d[i])):
				s1 += (len(d[i]) - j - 1) * d[i][j]
				sum_ += d[i][j]
				sq += d[i][j] ** 2
			s1 = s1 * (len(a) + 1)
			s2 = (sum_ ** 2 - sq) // 2
			c += s1 - s2
	print(c)


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = defaultdict(list)
		for (i, v) in enumerate(a):
			b[v].append(i)
		ans = 0
		for i in b:
			z = b[i]
			c = [0] * (len(z) + 1)
			for j in range(len(z) - 1, -1, -1):
				c[j] = c[j + 1] + (n - z[j])
			for j in range(len(z) - 1):
				ans += c[j + 1] * (z[j] + 1)
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	dic = {}
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	ans = 0
	for i in range(n):
		r = n - i
		if a[i] in dic:
			ans += dic[a[i]] * r
		else:
			dic[a[i]] = 0
		dic[a[i]] += i + 1
	ANS.append(str(ans))
print('\n'.join(ANS))


def solve():
	n = input()
	n = int(n)
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	dp = [0]
	d = {a[0]: 1}
	c = {a[0]: 1}
	ans = 0
	for i in range(1, n):
		x = a[i]
		dp.append(dp[i - 1])
		if x in d:
			y = d[x]
			d[x] += i + 1
			dp[i] += y
		else:
			d[x] = i + 1
		ans += dp[i]
	print(ans)

def main():
	t = input()
	t = int(t)
	for i in range(t):
		solve()
main()


from sys import stdin
from collections import defaultdict as dd
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	sms = dd(lambda : 0)
	res = 0
	for i in range(n):
		res += sms[a[i]] * (n - i)
		sms[a[i]] += i + 1
	print(res)


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
for _ in range(inp()):
	n = inp()
	x = ip()
	dt = {i: [] for i in list(set(x))}
	for i in range(n):
		dt[x[i]].append(i)
	ans = 0
	for ii in dt:
		if len(dt[ii]) > 1:
			y = dt[ii]
			r = [n - jj for jj in y]
			t = sum(r)
			for i in range(len(y)):
				t -= r[i]
				ans += (y[i] + 1) * t
	print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	prev = {}
	dp = [0 for i in range(n)]
	for i in range(n):
		if i > 0:
			dp[i] = dp[i - 1]
		if a[i] in prev:
			dp[i] += prev[a[i]]
			prev[a[i]] += i + 1
		else:
			prev[a[i]] = i + 1
		ans += dp[i]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	last_index = dict()
	h = dict()
	g = dict()
	f = dict()
	for i in range(n):
		curr = a[i]
		if curr in last_index:
			(f[curr], g[curr], h[curr]) = (f[curr] + g[curr] * (i + 1 - last_index[curr]), g[curr] + h[curr], h[curr] + i + 1)
			last_index[curr] = i + 1
		else:
			(f[curr], g[curr], h[curr], last_index[curr]) = (0, 0, i + 1, i + 1)
	res = 0
	for key in last_index:
		f[key] += g[key] * (n - last_index[key] + 1)
		res += f[key]
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	ans = 0
	tmp = 0
	for i in range(n):
		if arr[i] in d:
			tmp += d[arr[i]]
		else:
			d[arr[i]] = 0
		d[arr[i]] += i + 1
		ans += tmp
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd

def solve():
	n = int(input())
	L = list(map(int, input().split()))
	d = dd(int)
	ans = 0
	for i in range(n):
		ans += d[L[i]] * (n - i)
		d[L[i]] += i + 1
	print(ans)
for _ in range(int(input())):
	solve()


import sys
from collections import defaultdict
CONST = 100030001

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(input())
while t:
	n = int(input())
	arr = list(get_ints())
	hm = defaultdict(lambda : [])
	for (idx, num) in enumerate(arr):
		hm[num].append(idx)
	ans = 0
	for (k, v) in hm.items():
		if len(v) <= 1:
			continue
		ps = 0
		for idx in v:
			ans += ps * (n - idx)
			ps += idx + 1
	print(ans)
	t -= 1


T = int(input())
for x in range(T):
	n = int(input())
	dict = {}
	vals = list(map(int, input().split()))
	cnt = 0
	for a in vals:
		if a not in dict.keys():
			dict[a] = []
		dict[a].append(cnt)
		cnt += 1
	ans = 0
	for (key, value) in dict.items():
		list1 = value
		m = len(value)
		sumList = [0] * m
		sumList[0] = list1[0] + 1
		for i in range(1, m):
			sumList[i] = sumList[i - 1] + list1[i] + 1
		for i in range(1, m):
			after = n - list1[i]
			ans += after * sumList[i - 1]
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	(*a,) = map(int, input().split())
	d = {}
	for (index, i) in enumerate(a):
		if i in d:
			d[i].append(index)
		else:
			d[i] = [index]
	ans = 0
	for values in d.values():
		xs = 0
		for y in values:
			ans += xs * (n - y)
			xs += y + 1
	print(ans)
for i in range(int(input())):
	solve()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
from math import *
from bisect import *
from heapq import *
from collections import defaultdict as dd
from collections import OrderedDict as odict
from collections import Counter as cc
from collections import deque
from itertools import groupby
sys.setrecursionlimit(20 * 20 * 20 * 20 + 10)
MAX = 10 ** 5

def solve():
	n = takein()
	arr = takeiar()
	dict_1 = dd(lambda : 0)
	ans = 0
	summ = 0
	for i in range(n):
		summ += dict_1[arr[i]]
		ans += summ
		dict_1[arr[i]] += i + 1
	print(ans)
	return

def main():
	global tt
	if not ONLINE_JUDGE:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	t = 1
	t = takein()
	for tt in range(1, t + 1):
		solve()
	if not ONLINE_JUDGE:
		print('Time Elapsed :', time.time() - start_time, 'seconds')
		sys.stdout.close()

def takein():
	return int(sys.stdin.readline().rstrip('\r\n'))

def takesr():
	return sys.stdin.readline().rstrip('\r\n')

def takeiar():
	return list(map(int, sys.stdin.readline().rstrip('\r\n').split()))

def takesar():
	return list(map(str, sys.stdin.readline().rstrip('\r\n').split()))

def takeivr():
	return map(int, sys.stdin.readline().rstrip('\r\n').split())

def takesvr():
	return map(str, sys.stdin.readline().rstrip('\r\n').split())

def ispalindrome(s):
	return s == s[::-1]

def invert(bit_s):
	temp = int(bit_s, 2)
	inverse_s = temp ^ 2 ** (len(bit_s) + 1) - 1
	rslt = bin(inverse_s)[3:]
	return str(rslt)

def counter(a):
	q = [0] * max(a)
	for i in range(len(a)):
		q[a[i] - 1] = q[a[i] - 1] + 1
	return q

def counter_elements(a):
	q = dict()
	for i in range(len(a)):
		if a[i] not in q:
			q[a[i]] = 0
		q[a[i]] = q[a[i]] + 1
	return q

def string_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
	return q

def factorial(n, m=1000000007):
	q = 1
	for i in range(n):
		q = q * (i + 1) % m
	return q

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.append(i)
			q.append(n // i)
	return list(sorted(list(set(q))))

def prime_factors(n):
	q = []
	while n % 2 == 0:
		q.append(2)
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			q.append(i)
			n = n // i
	if n > 2:
		q.append(n)
	return list(sorted(q))

def transpose(a):
	(n, m) = (len(a), len(a[0]))
	b = [[0] * n for i in range(m)]
	for i in range(m):
		for j in range(n):
			b[i][j] = a[j][i]
	return b

def power_two(x):
	return x and (not x & x - 1)

def ceil(a, b):
	return -(-a // b)

def seive(n):
	a = [1]
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p = p + 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)
	return a

def isprime(n):
	if n > 2 and (not n % 2) or n == 1:
		return False
	for i in range(3, int(n ** 0.5 + 1), 2):
		if not n % i:
			return False
	return True
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
import inspect, re

def varname(p):
	for line in inspect.getframeinfo(inspect.currentframe().f_back)[3]:
		m = re.search('\\bvarname\\s*\\(\\s*([A-Za-z_][A-Za-z0-9_]*)\\s*\\)', line)
		if m:
			return m.group(1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		d = {}
		for i in range(n):
			if a[i] not in d:
				d[a[i]] = []
			d[a[i]].append(i)
		ans = 0
		for i in d.keys():
			s = n * len(d[i]) - sum(d[i])
			for j in range(len(d[i])):
				s -= n - d[i][j]
				ans += (d[i][j] + 1) * s
		print(ans)
	return
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	lefts = {}
	ans = 0
	for i in range(n):
		num = a[i]
		if num in lefts:
			ans += lefts[num] * (n - i)
			lefts[num] += i + 1
		else:
			lefts[num] = i + 1
	print(ans)


import sys
input = sys.stdin.readline
import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		if arr[i] in d:
			d[arr[i]].append(i)
		else:
			d[arr[i]] = [i]
	ans = 0
	for key in d:
		l = len(d[key])
		suff = n - d[key][l - 1]
		for i in range(l - 2, -1, -1):
			ans = ans + (d[key][i] + 1) * suff
			suff = suff + n - d[key][i]
	print(ans)


from math import *
from sys import *
from bisect import *
from collections import *
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	b = []
	for i in range(n):
		b.append([a[i], i])
	b.sort()
	m = 0
	ans = 0
	for i in range(1, n):
		if b[i][0] == b[i - 1][0]:
			m += b[i - 1][1] + 1
			ans += (n - b[i][1]) * m
		else:
			m = 0
	print(ans)


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
import heapq
I = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'
mod = 10 ** 9 + 7

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def main():
	ans = ''
	for _ in range(ii()):
		n = ii()
		arr = li()
		d = defaultdict(list)
		for i in range(n):
			d[arr[i]].append(i + 1)
		cnt = 0
		for i in d:
			le = len(d[i])
			if le > 1:
				pf = 0
				for j in range(1, le):
					pf += d[i][j - 1]
					cnt += pf * (n - d[i][j] + 1)
		ans += str(cnt) + '\n'
	print(ans)
main()


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split()]
	return res

def read_list_of_ints_zero():
	return [int(val) - 1 for val in input().rstrip('\n').split()]

def read_str():
	return input().rstrip()

def main():
	tests = read_one_int()
	for _ in range(tests):
		n = read_one_int()
		elements = read_list_of_ints()
		stat = {}
		cur_res = 0
		res = 0
		for (i, el) in enumerate(elements):
			if el in stat:
				cur_res += stat[el]
			else:
				stat[el] = 0
			stat[el] += i + 1
			res += cur_res
		print(res)
main()


for m in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = {}
	Res = [0] * N
	for i in range(N):
		Res[i] = Res[i - 1]
		if A[i] in B:
			Res[i] += B[A[i]]
			B[A[i]] += i + 1
		else:
			B[A[i]] = i + 1
	print(sum(Res))


import sys
Z = sys.stdin.readline
from collections import defaultdict as D
O = []
for _ in range(int(Z())):
	n = int(Z())
	a = [*map(int, Z().split())]
	d = D(int)
	s = 0
	for i in range(n):
		s += (n - i) * d[a[i]]
		d[a[i]] += i + 1
	O.append(f'{s}')
print('\n'.join(O))


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def fi():
	return float(input())

def si():
	return input()

def msi():
	return map(str, input().split())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def lsi():
	return list(msi())

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	return x * y // gcd(x, y)
mod = 1000000007

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def ceil2(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def modu(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return -999999999
	else:
		return inv * a % m
from math import log, factorial, cos, tan, sin, radians, floor, sqrt, ceil, log2
import bisect
import random
import string
from decimal import *
getcontext().prec = 50
abc = 'abcdefghijklmnopqrstuvwxyz'
pi = 3.141592653589793

def gcd1(a):
	if len(a) == 1:
		return a[0]
	ans = a[0]
	for i in range(1, len(a)):
		ans = gcd(ans, a[i])
	return ans

def mykey(x):
	return len(x)

def checkper_sq(n):

	def check(n, mod):
		for i in range(mod):
			if i * i % mod == n % mod:
				return True
		return False
	for i in range(3, 101):
		if not check(n, i):
			return False
	return True

def main():
	l = [0] * 100005
	l[1] = 0
	for i in range(2, len(l)):
		l[i] = l[i - 1] + i * (i - 1) // 2
	for _ in range(ii()):
		n = ii()
		a = li()
		ans = 0
		d = dict()
		l = dict()
		p = -1
		c = 1
		for i in range(n):
			if a[i] not in d:
				if a[i] in l:
					l[a[i]] += i + 1
				else:
					l[a[i]] = i + 1
				d[a[i]] = 1
			else:
				ans += (n - i) * l[a[i]]
				l[a[i]] += i + 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from bisect import bisect, bisect_left
from collections import *
from heapq import *
from math import gcd, ceil, sqrt, floor, inf
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

class UF:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n
		self.size = AI(n, 1)
		self.edge = A(n)

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			self.edge[pu] += 1
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			self.edge[pu] += self.edge[pv] + 1
			self.size[pu] += self.size[pv]
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv
			self.edge[pv] += self.edge[pu] + 1
			self.size[pv] += self.size[pu]

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = AI(n, inf)
	d[s] = 0
	heap = [(0, s)]
	vis = A(n)
	while heap:
		(dis, u) = heappop(heap)
		if vis[u]:
			continue
		vis[u] = 1
		for (v, w) in graph[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	n = N()
	a = RLL()
	c = Counter()
	ans = 0
	for (i, v) in enumerate(a):
		if v in c:
			ans += c[v] * (n - i)
		c[v] += i + 1
	print(ans)


def solve(n, arr):
	dic = {}
	for i in range(n):
		if arr[i] not in dic:
			dic[arr[i]] = []
		dic[arr[i]].append(i)
	count = 0
	for value in dic.values():
		if len(value) > 1:
			temp2 = 0
			for i in value:
				temp2 += n - i
			for i in value:
				temp2 -= n - i
				temp1 = i + 1
				count += temp1 * temp2
	return count
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	result = solve(n, arr)
	print(result)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	ans = 0
	fin = 0
	dicti = {}
	for i in range(n):
		if l[i] in dicti:
			ans += dicti[l[i]]
		else:
			dicti[l[i]] = 0
		dicti[l[i]] += i + 1
		fin += ans
	print(fin)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	from collections import defaultdict
	dic = defaultdict(list)
	for x in range(n):
		dic[arr[x]].append(x)
	ans = 0
	for x in dic:
		pre = [0] * len(dic[x])
		pre[-1] = n - dic[x][-1]
		for z in range(len(dic[x]) - 2, -1, -1):
			pre[z] = pre[z + 1] + (n - dic[x][z])
		for z in range(len(dic[x]) - 1):
			ans += (dic[x][z] + 1) * pre[z + 1]
	print(ans)


def process(S):
	d = {}
	answer = 0
	n = len(S)
	for i in range(n):
		x = S[i]
		if x not in d:
			d[x] = {'Sum': 0, 'Length': 0}
		answer += (d[x]['Sum'] + d[x]['Length']) * (n - i)
		d[x]['Sum'] += i
		d[x]['Length'] += 1
	return answer
t = int(input())
for i in range(t):
	n = int(input())
	S = [int(x) for x in input().split()]
	print(process(S))