Sherlock is given an array of $N$ integers ($A_0,A_1...A_{N-1}$ by Watson. Now Watson asks Sherlock how many different pairs of indices $\boldsymbol{i}$ and $j$ exist such that $\boldsymbol{i}$ is not equal to $j$ but $A_i$ is equal to $A_j$.     

That is, Sherlock has to count the total number of pairs of indices $(i,j)$ where  $A_i$=$A_j$ AND $i\neq j$.

Input Format 

The first line contains $\mathbf{T}$, the number of test cases. $\mathbf{T}$ test cases follow. 

Each test case consists of two lines; the first line contains an integer $N$, the size of array, while the next line contains $N$ space separated integers.

Output Format 

For each test case, print the required answer on a different line. 

Constraints 

$1\leq T\leq10$ 

$1\leq N\leq$10^5$$ 

$1\leq A[i]\leq$10^6$$  

Sample input

2
3
1 2 3
3
1 1 2

Sample output   

0
2

Explanation 

In the first test case, no two pair of indices exist which satisfy the given condition. 

In the second test case as A[0] = A[1] = 1, the pairs of indices (0,1) and (1,0) satisfy the given condition.

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
import collections, math, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = sorted(map(int, sys.stdin.readline().split()))
	c = collections.Counter(A)
	print(sum((v * (v - 1) for v in c.values())))


t = int(input())
for case in range(t):
	n = int(input())
	s = [int(x) for x in input().split(' ')]
	d = {}
	for c in s:
		d[c] = d[c] + 1 if c in d.keys() else 1
	res = 0
	for c in (x for x in d if d[x] > 1):
		res += d[c] * (d[c] - 1)
	print(res)


def call():
	n = int(input())
	arr = []
	i = 0
	val1 = input()
	val = val1.split()
	for i in range(0, n):
		arr.append(int(val[i]))
	arr.sort()
	count = 0
	i = 0
	sum1 = 0
	now = arr[0]
	for i in range(0, n):
		if now == arr[i]:
			count += 1
		else:
			now = arr[i]
			sum1 += count * (count - 1)
			count = 1
	sum1 += count * (count - 1)
	return sum1
t = int(input())
k = 0
for k in range(0, t):
	print(call())


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	a.sort()
	i = 0
	s = 0
	l = len(a)
	while i < l:
		x = 0
		p = a[i]
		while i < l and p == a[i]:
			i += 1
			x += 1
		if x > 1:
			s += x * (x - 1)
	print(s)


import math
T = int(input())
for i in range(T):
	N = int(input())
	num_list = list(map(int, input().split()))
	num_freq = {}
	for num in num_list:
		if num in num_freq:
			num_freq[num] += 1
		else:
			num_freq[num] = 1
	count = 0
	for freq in num_freq.values():
		if freq == 2:
			count += 2
		elif freq > 2:
			count += freq * (freq - 1)
	print(int(count))


from collections import defaultdict
case = input()
for i in range(int(case)):
	l = input()
	a = input()
	a = a.split()
	d = defaultdict(int)
	for j in range(int(l)):
		d[int(a[j])] += 1
	tot = 0
	for j in d.keys():
		n = d[j]
		tot += n * (n - 1)
	print(tot)


t = int(input())
ans = ''
for i in range(0, t):
	n = int(input())
	z = [int(x) for x in input().split()]
	dp = [0] * 1000001
	for i in range(0, len(z)):
		dp[z[i]] += 1
	t = 0
	for j in range(0, len(dp)):
		t += int(dp[j] * (dp[j] - 1) / 2)
	ans += str(2 * t) + '\n'
print(ans)


from collections import defaultdict

def getval(n):
	return 0 if n == 1 else n * (n - 1)
T = int(input())
for _i in range(T):
	N = int(input())
	values = map(int, input().split())
	d = defaultdict(int)
	for x in values:
		d[x] += 1
	print(sum((getval(n) for n in d.values())))


test = int(input())
out = []
for k in range(test):
	times = int(input())
	number = str(input())
	number = number.split()
	number = list(map(int, number))
	number.sort()
	count = 0
	from itertools import groupby
	new = [len(list(group)) for (key, group) in groupby(number)]
	for h in range(len(new)):
		num = new[h]
		count += num * (num - 1)
	out.append(count)
out.reverse()
while len(out) != 0:
	print(out.pop())


from collections import Counter
for i in range(int(input())):
	N = int(input())
	C = Counter(list(map(int, input().split())))
	print(sum((v ** 2 - v for v in C.values())))


def getPairs(nums):
	checkerDict = {}
	for num in nums:
		checkerDict[num] = checkerDict[num] + 1 if num in checkerDict else 1
	total = 0
	for (k, v) in checkerDict.items():
		if v != 1:
			total += v * (v - 1)
	return total
count = int(input())
for i in range(count):
	n = int(input())
	nums = [int(i) for i in input().split(' ')]
	print(getPairs(nums))


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	c = Counter(map(int, input().split()))
	p = 0
	for i in c.values():
		p += (i - 1) * i
	print(p)


def f(A):
	A.sort()
	res = 0
	c = 1
	for i in range(1, len(A)):
		if A[i] != A[i - 1]:
			res += c * (c - 1) // 2
			c = 1
		else:
			c += 1
	res += c * (c - 1) // 2
	return 2 * res
for _ in range(int(input())):
	input()
	print(f([int(i) for i in input().split()]))


def matching_pairs(ar, n):
	d = {}
	for elem in ar:
		if not elem in d:
			d[elem] = 1
		else:
			d[elem] += 1
	total = 0
	for val in d.values():
		total += val * (val - 1)
	return total
tests = int(input())
for i in range(0, tests):
	n = int(input())
	ar = [int(i) for i in input().split()]
	print(matching_pairs(ar, n))


from collections import Counter
from math import factorial
cases = int(input())
for case in range(cases):
	c = Counter()
	numbers = int(input())
	for x in map(int, input().split()):
		c[x] += 1
	total = 0
	for key in c:
		if c[key] > 1:
			total += factorial(c[key]) // factorial(c[key] - 2)
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	ar = [int(i) for i in input().strip().split()]
	D = {}
	for x in ar:
		if x not in D.keys():
			D[x] = 1
			continue
		D[x] += 1
	res = 0
	for x in D.keys():
		val = D[x]
		if val > 1:
			res += val * (val - 1)
	print(res)


for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	flag = 1
	pair = 0
	for x in a:
		if flag == 1:
			pre = x
			flag = 0
			count = 1
			continue
		elif pre == x:
			count += 1
		else:
			pair += count * (count - 1) / 2
			count = 1
			pre = x
	pair += count * (count - 1) / 2
	print(int(pair * 2))


for t in range(int(input())):
	n = int(input())
	m = {}
	for x in [int(v) for v in input().split()]:
		if x in m:
			m[x] = m[x] + 1
		else:
			m[x] = 1
	s = 0
	for (k, v) in m.items():
		s += v * (v - 1)
	print(s)


import sys
cases = int(sys.stdin.readline())
for i in range(cases):
	leng = int(sys.stdin.readline())
	nums = sys.stdin.readline().strip().split()
	nums = list(map(int, nums))
	counts = {}
	tot = 0
	for j in nums:
		if j in counts:
			counts[j] += 1
		else:
			counts[j] = 1
	for j in counts.keys():
		tot += counts[j] * (counts[j] - 1)
	print(tot)


from collections import Counter
T = int(input())
for t in range(T):
	N = int(input())
	arr = tuple((int(n) for n in input().split()))
	total = 0
	for (elem, cnt) in Counter(arr).items():
		total += cnt * (cnt - 1)
	print(total)


T = int(input())
for _ in range(T):
	N = input()
	a = [int(i) for i in str.split(input())]
	a.sort()
	cnt = 1
	pairs = 0
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			cnt += 1
		else:
			pairs += cnt * (cnt - 1)
			cnt = 1
	pairs += cnt * (cnt - 1)
	print(int(pairs))


def maxPairs(sortedList):
	if len(sortedList) < 2:
		return 0
	output = 0
	val = sortedList[0]
	i = 1
	while i < len(sortedList):
		j = i
		while j < len(sortedList) and val == sortedList[j]:
			j += 1
		output += (j - i) * (j - i + 1)
		if j < len(sortedList) - 1:
			i = j + 1
			val = sortedList[j]
		else:
			break
	return output

def mergesort(list):
	if len(list) == 1:
		return list
	half = len(list) // 2
	left = list[:half]
	right = list[half:]
	return merge(mergesort(left), mergesort(right))

def merge(array1, array2):
	i = 0
	j = 0
	output = []
	while i < len(array1) and j < len(array2):
		if array1[i] <= array2[j]:
			output.append(array1[i])
			i += 1
		else:
			output.append(array2[j])
			j += 1
	if i < len(array1):
		while i < len(array1):
			output.append(array1[i])
			i += 1
	else:
		while j < len(array2):
			output.append(array2[j])
			j += 1
	return output
numInputs = int(input())
for i in range(numInputs):
	N = int(input())
	array = [int(x) for x in input().split()]
	sorted = mergesort(array)
	print(maxPairs(sorted))


from operator import mul
from fractions import Fraction
from collections import Counter
from functools import reduce

def nCk(n, k):
	return int(reduce(mul, (Fraction(n - i, i + 1) for i in range(k)), 1))
for case in range(int(input())):
	N = int(input())
	c = Counter(map(int, input().split()))
	print(sum((nCk(x, 2) * 2 for x in c.values() if x > 1)))


t = int(input())
for i in range(t):
	n = int(input())
	A = [0] * 1000001
	li = list(map(int, input().strip().split(' ')))
	count = 0
	for j in range(n):
		A[li[j]] = A[li[j]] + 1
	for j in range(n):
		val = 1
		if A[li[j]] > 1:
			val = A[li[j]] * (A[li[j]] - 1)
			A[li[j]] = 0
			count = count + val
	print(count)


output = []
num_testcases = int(input())
for _ in range(num_testcases):
	input()
	num_cases = 0
	tc_dict = {}
	for i in input().split():
		if i not in tc_dict:
			tc_dict[i] = 1
		else:
			tc_dict[i] += 1
	for j in tc_dict:
		if tc_dict[j] > 1:
			num_cases += (tc_dict[j] - 1) * tc_dict[j]
	output.append(num_cases)
for o in output:
	print(o)


def solve():
	n = int(input())
	ar = [int(x) for x in input().strip().split()]
	from collections import defaultdict
	countDict = defaultdict(lambda : 0)
	count = 0
	for item in ar:
		count += countDict[item] * 2
		countDict[item] += 1
	print(count)
t = int(input())
for i in range(t):
	solve()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	curent = None
	countPairs = 0
	countSame = 0
	for ai in a:
		if ai == curent:
			countSame += 1
		else:
			if countSame > 1:
				countPairs += countSame * (countSame - 1)
			countSame = 1
			curent = ai
	if countSame > 1:
		countPairs += countSame * (countSame - 1)
	print(countPairs)


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


def solve(A):
	A.sort()
	count = 0
	(p, c) = (A[0], 0)
	for a in A:
		if a == p:
			c += 1
		else:
			count += c * (c - 1)
			c = 1
		p = a
	count += c * (c - 1)
	return count
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(_) for _ in input().split()]
	print(solve(A))


from math import factorial
T = int(input())
for i in range(T):
	inputs = {}
	total = 0
	N = int(input())
	inpStr = input()
	array = inpStr.split()
	for i in array:
		key = int(i)
		if key in inputs:
			inputs[key] += 1
		else:
			inputs[key] = 1
	keys = inputs.keys()
	for key in keys:
		if inputs[key] > 1:
			total += factorial(inputs[key]) / factorial(inputs[key] - 2)
	print(int(total))


from collections import Counter

def main():
	for case in range(int(input())):
		n = int(input())
		numbers = [int(x) for x in str(input()).split()]
		print(check(numbers))

def check(numbers):
	if len(numbers) == 1:
		return 0
	c = Counter(numbers)
	count = 0
	for key in list(set(c.keys())):
		count += 2 * sum((i + 1 for i in range(c[key] - 1)))
	return count
main()


from collections import Counter

def abtwo(n):
	return n * (n - 1)

def equalValue(arr):
	c = Counter(arr)
	total = 0
	for k in c.keys():
		total += abtwo(c[k])
	return total

def main():
	T = int(input())
	while T != 0:
		n = int(input())
		arr = [int(x) for x in input().split()]
		print(equalValue(arr))
		T -= 1
main()


def combine(v):
	return v * (v - 1)
T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split()]
	buckets = [0] * (10 ** 6 + 1)
	for v in arr:
		buckets[v] += 1
	sum = 0
	for v in buckets:
		sum += combine(v)
	print(sum)


from itertools import groupby

def test_case(n, a):
	a = sorted(a)
	counts = [len(list(g)) for (k, g) in groupby(a)]
	result = 0
	for c in counts:
		result += c * (c - 1)
	return result
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(test_case(n, a))


from collections import Counter
T = int(input())
for _ in range(T):
	N = int(input())
	x = (int(s) for s in input().split())
	c = Counter(x)
	print(sum((n * (n - 1) for (_, n) in c.items())))


import collections

def indices_exist(a):
	indices = 0
	counts = collections.defaultdict(int)
	for v in a:
		counts[v] += 1
	for c in counts.values():
		indices += c * (c - 1)
	return indices
t = int(input().strip())
for _ in range(t):
	input()
	a = list(map(int, input().strip().split()))
	print(indices_exist(a))


import sys
import math
t = int(sys.stdin.readline().strip())
for tests in range(t):
	n = int(sys.stdin.readline().strip())
	a = [int(x) for x in sys.stdin.readline().split()]
	d = {}
	for x in a:
		if x in d.keys():
			d[x] = d[x] + 1
		else:
			d[x] = 1
	answer = 0
	for k in d.keys():
		if d[k] > 1:
			answer += d[k] * (d[k] - 1)
	print(answer)


t = int(input())
i = 0
while i < t:
	N = int(input())
	k = input().split()
	for pi in range(0, len(k)):
		k[pi] = int(k[pi])
	array = [0] * (max(k) + 1)
	for ele in k:
		array[ele] = array[ele] + 1
	sum = 0
	for eke in array:
		if eke > 1:
			sum = sum + eke * (eke - 1)
	print(sum)
	i = i + 1


import sys

def inp():
	return list(map(int, input().split()))
t = inp()[0]
for _ in range(t):
	n = inp()[0]
	a = inp()
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	print(d, file=sys.stderr)
	p = 0
	for i in d:
		if d[i] > 1:
			p += d[i] * (d[i] - 1)
	print(p)


numinputs = int(input())
from functools import reduce
ctable = {}

def nCk(n, k):
	try:
		rv = ctable[n]
	except:
		rv = ctable[n] = int(reduce(lambda x, y: x * y, (Fraction(n - i, i + 1) for i in range(k)), 1))
	return rv
from fractions import Fraction
for dummy in range(numinputs):
	n = int(input())
	a = [int(val) for val in input().split()]
	dc = {}
	for i in range(n):
		dc[i] = a[i]
	sorteddc = sorted(dc, key=lambda x: dc[x])
	count = 0
	currcount = 0
	ind = 0
	while True:
		if ind == n - 1:
			count = count + nCk(currcount + 1, 2)
			break
		if dc[sorteddc[ind]] == dc[sorteddc[ind + 1]]:
			currcount = currcount + 1
		else:
			count = count + nCk(currcount + 1, 2)
			currcount = 0
		ind = ind + 1
	print(2 * count)


from collections import Counter
T = int(input())
for _ in range(T):
	input()
	c = Counter(input().split())
	s = 0
	for k in c.keys():
		s += c[k] * (c[k] - 1)
	print(s)


def getPair(arr, size):
	count = 1
	result = 0
	for i in range(0, size - 1):
		if arr[i] == arr[i + 1]:
			count = count + 1
		else:
			result = result + count * (count - 1)
			count = 1
	result = result + count * (count - 1)
	print(result)

def quickSort(arr, lo, hi):
	if lo >= hi:
		return
	pivot = arr[hi]
	size = hi - lo + 1
	mid = lo
	for i in range(size):
		if arr[i] <= pivot:
			swap(arr, lo + i, mid)
			mid = mid + 1
			if mid > hi:
				mid = hi
	swap(arr, mid, hi)
	quickSort(arr, lo, mid - 1)
	quickSort(arr, mid + 1, hi)

def swap(arr, start, end):
	temp = arr[start]
	arr[start] = arr[end]
	arr[end] = temp
test = int(input())
for i in range(test):
	size = int(input())
	arr = list(map(int, input().split(' ')))
	arr.sort()
	getPair(arr, size)


from collections import defaultdict

def zero():
	return int(0)
testcases = int(input())
for test in range(testcases):
	length = int(input())
	seen = defaultdict(zero)
	numbers = [int(i) for i in input().split()]
	for i in numbers:
		seen[i] += 1
	pairs = 0
	for key in seen:
		if seen[key] > 1:
			pairs += seen[key] * (seen[key] - 1)
	print(pairs)


from collections import Counter
for _ in range(int(input())):
	(n, ar) = (input(), Counter(map(int, input().split())))
	print(sum([i * (i - 1) for i in ar.values()]))


T = int(input())
for _ in range(T):
	count_dict = {}
	result = 0
	N = int(input())
	arr = [int(x) for x in input().split()]
	for elem in arr:
		if elem in count_dict:
			count_dict[elem] += 1
		else:
			count_dict[elem] = 1
	for elem in count_dict.keys():
		occurences = count_dict[elem]
		result += occurences * (occurences - 1)
	print(result)


T = int(input())
for _ in range(T):
	count_dict = {}
	result = 0
	N = int(input())
	arr = [int(x) for x in input().split()]
	for elem in arr:
		if elem in count_dict:
			count_dict[elem] += 1
		else:
			count_dict[elem] = 1
	for elem in count_dict.keys():
		occurences = count_dict[elem]
		result += occurences * (occurences - 1)
	print(result)


def count_pairs(input_nums):
	if len(input_nums) <= 1:
		return 0
	nums = sorted(input_nums)
	prev = nums[0]
	group_count = 1
	result = 0
	for i in range(1, len(nums)):
		if prev != nums[i]:
			result += group_count * (group_count - 1)
			group_count = 1
		else:
			group_count += 1
		prev = nums[i]
	result += group_count * (group_count - 1)
	return result

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		input_nums = input().split(' ')
		nums = [int(i) for i in input_nums]
		print(count_pairs(nums))
main()


from collections import Counter
for _ in range(int(input())):
	(n, ar) = (input(), Counter(map(int, input().split())))
	print(sum([i * (i - 1) for i in ar.values()]))


from collections import Counter
for _ in range(int(input())):
	(n, ar) = (input(), Counter(map(int, input().split())))
	print(sum([i * (i - 1) for i in ar.values()]))


from collections import Counter
import math
T = int(input())
result = ''
for i in range(0, T):
	N = input()
	pairCount = 0
	numberList = Counter(map(int, input().split(' ')))
	result += str(sum([i * (i - 1) for i in numberList.values()])) + '\n'
print(result)


from collections import defaultdict
T = int(input())
for x in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	D = defaultdict(int)
	count = 0
	for n in A:
		D[n] += 1
	for n in D:
		if D[n] > 1:
			count += D[n] * (D[n] - 1)
	print(count)


from collections import Counter
for _ in range(int(input())):
	(n, ar) = (input(), Counter(map(int, input().split())))
	print(sum([i * (i - 1) for i in ar.values()]))


import io
import sys

def pairs(numbers):
	numbers.sort()
	pairs_number = 0
	duplicates = 1
	i = 0
	for j in range(1, len(numbers)):
		if numbers[i] == numbers[j]:
			duplicates += 1
		else:
			pairs_number += duplicates * (duplicates - 1)
			duplicates = 1
			i = j
	pairs_number += duplicates * (duplicates - 1)
	return pairs_number

def test_consecutive_duplicates():
	assert 0 == pairs([])
	assert 0 == pairs([1])
	assert 0 == pairs([1, 2])
	assert 2 == pairs([1, 1])
	assert 2 == pairs([1, 1, 2])
	assert 4 == pairs([1, 1, 2, 2])
	assert 4 == pairs([2, 1, 2, 1])
	assert 12 == pairs([1, 1, 1, 1])

def parse_inputs(stream):
	cases_number = int(stream.readline())
	for i in range(cases_number):
		stream.readline()
		numbers = [int(n) for n in stream.readline().split()]
		yield numbers

def calculate(input_):
	return pairs(input_)

def print_result(stream, results):
	stream.write('%d\n' % results)

def test_parsing_inputs():
	s = io.StringIO('1\n2\n3 4')
	inputs = list(parse_inputs(s))
	assert len(inputs) == 1
	assert [3, 4] == inputs[0]
	s = io.StringIO('2\n2\n3 4\n3\n1 2 3\n')
	inputs = list(parse_inputs(s))
	assert len(inputs) == 2
	assert [3, 4] == inputs[0]
	assert [1, 2, 3] == inputs[1]

def test_print_output():
	s = io.StringIO()
	print_result(s, 10)
	assert '10\n' == s.getvalue()

def test_calculate_sample_inputs():
	pass

def main():
	for input_ in parse_inputs(sys.stdin):
		results = calculate(input_)
		print_result(sys.stdout, results)
main()


for _ in range(int(input())):
	n = int(input())
	numbers = sorted([int(x) for x in input().strip().split()])
	last_number = -1
	repetitions = []
	for number in numbers:
		if number == last_number:
			repetitions[-1] += 1
		else:
			repetitions.append(1)
		last_number = number
	pairs = map(lambda x: x * (x - 1), repetitions)
	print(sum(pairs))


def checkpairs(l):
	d = {}
	n = 0
	for i in l:
		if i in d:
			n += 2 * d[i]
			d[i] = d[i] + 1
		else:
			d[i] = 1
	print(n)
n = int(input())
for _ in range(n):
	x = int(input())
	ar = [int(y) for y in input().split(' ')]
	checkpairs(ar)


from collections import defaultdict

def count_occurences(lst):
	count = defaultdict(int)
	for i in range(len(lst)):
		count[lst[i]] += 1
	return count

def pairs(lst):
	count = count_occurences(lst)
	result = 0
	for val in count.values():
		if val > 1:
			result += val * (val - 1)
	return result
num_cases = int(input())
for i in range(num_cases):
	length = input()
	str_arr = input().split(' ')
	lst = list(map(int, str_arr))
	print(pairs(lst))


from collections import Counter
get_int = lambda : int(input())
get_list = lambda : [int(s) for s in input().split()]
for _ in range(get_int()):
	get_int()
	c = Counter(get_list())
	print(sum((v * (v - 1) for (k, v) in c.items())))


case_count = int(input())
cases = [None for _ in range(case_count)]
for i in range(case_count):
	_ = input()
	cases[i] = [int(i) for i in input().split()]
for case in cases:
	count = 0
	case.sort()
	previous = -1
	same_count = 0
	for i in case:
		if i == previous:
			count += 2 * same_count
			same_count += 1
		else:
			previous = i
			same_count = 1
	print(count)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	A.sort()
	count = 0
	val = A[0]
	j = 0
	for i in A:
		if i == val:
			j += 1
		else:
			if j > 1:
				count += j * j - j
			val = i
			j = 1
	if j > 1:
		count += j * j - j
	print(count)


import collections, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = sorted(map(int, sys.stdin.readline().split()))
	print(sum((v * (v - 1) for v in collections.Counter(A).values())))


t = int(input())
for _ in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	pair = dict()
	for number in numbers:
		pair[number] = pair.setdefault(number, 0) + 1
	pairs = 0
	for key in pair:
		if pair[key] > 1:
			pairs = pairs + pair[key] * (pair[key] - 1)
	print(pairs)


def fab(a):
	sum = 0
	for j in range(1, a + 1):
		sum += j
	return sum
t = int(input())
for i in range(0, t):
	n = int(input())
	arr = []
	for d in input().split():
		arr.append(int(d))
	arr.sort()
	count = 0
	last = -1
	freq = 1
	for d in arr:
		if d == last:
			freq += 1
		else:
			if freq > 1:
				count += 2 * fab(freq - 1)
			freq = 1
		last = d
	if freq > 1:
		count += 2 * fab(freq - 1)
	print(count)


def create_dict(li):
	di = dict()
	for i in li:
		di[i] = di.get(i, 0) + 1
	return di
for i in range(int(input())):
	input()
	li = [int(x) for x in input().split()]
	t = sum([y * (y - 1) for (x, y) in create_dict(li).items() if y > 1])
	print(t)


from collections import Counter
for _ in range(int(input())):
	arraySize = int(input())
	array = [int(x) for x in input().split(' ')]
	count = Counter(array)
	print(sum((n * (n - 1) for n in count.values())))


from collections import Counter

def numpairs(nums):
	return sum((c * (c - 1) for (num, c) in Counter(nums).items()))
n = int(input())
for _ in range(n):
	input()
	nums = [int(el) for el in input().split()]
	print(numpairs(nums))


def p(a, b):
	res = 1
	while b > 0:
		res = res * a
		a = a - 1
		b = b - 1
	return res
t = int(input())
for i in range(t):
	n = int(input())
	array = [int(x) for x in input().split()]
	count = 0
	curr = 0
	array.sort()
	for i in range(len(array) - 1):
		if array[i] == array[i + 1]:
			curr += 1
		else:
			count += p(curr + 1, 2)
			curr = 0
	else:
		count += p(curr + 1, 2)
	print(count)


from collections import Counter
for _ in range(int(input())):
	input()
	l = list(map(int, input().split()))
	c = Counter(l)
	print(sum((c[i] * (c[i] - 1) for i in c)))


for _ in range(int(input())):
	n = int(input())
	nums = [int(x) for x in input().split()]
	total = 0
	counts = {}
	for num in nums:
		if num in counts:
			counts[num] += 1
		else:
			counts[num] = 1
	for c in counts:
		count = counts[c]
		if count > 1:
			total += count * (count - 1)
	print(total)


cases = int(input())
for _ in range(cases):
	N = int(input())
	A = [int(i) for i in input().split()]
	D = {}
	for i in A:
		if i in D:
			D[i] += 1
		else:
			D[i] = 1
	pairs = 0
	for i in D:
		if D[i] > 1:
			pairs += D[i] * (D[i] - 1)
	print(pairs)


from sys import stdin

def Factorial(Start, Min):
	Value = 1
	for x in range(Min, Start + 1):
		Value *= x
	return Value

def NChooseK(N, K):
	return Factorial(N, N - K + 1) / Factorial(K, 2)

def main():
	T = int(stdin.readline())
	for x in range(T):
		Answer = 0
		N = int(stdin.readline())
		Array = [int(x) for x in stdin.readline().split()]
		SameNumberGroups = {}
		Array.sort()
		Previous = -1
		for x in range(len(Array)):
			if Previous == Array[x]:
				if Array[x] in SameNumberGroups:
					SameNumberGroups[Array[x]] += 1
				else:
					SameNumberGroups[Array[x]] = 2
			Previous = Array[x]
		for x in SameNumberGroups.keys():
			Answer += NChooseK(SameNumberGroups[x], 2)
		print(int(Answer * 2))
main()


t = int(input())
res = []
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	freq = {}
	for i in l:
		if i in freq.keys():
			freq[i] += 1
		else:
			freq[i] = 1
	temp = 0
	for i in freq:
		temp += freq[i] * (freq[i] - 1)
	res.append(temp)
for i in res:
	print(i)


def nb_combi(n):
	return n * (n - 1)

def count_doubles(ar, size):
	count = 0
	table = {}
	for x in range(size):
		if ar[x] in table:
			table[ar[x]] += 1
		else:
			table[ar[x]] = 1
	for x in table.keys():
		count += nb_combi(table[x])
	return count

def main():
	t = int(input())
	for x in range(t):
		n = int(input())
		ar = list(map(int, input().split()))
		print(count_doubles(ar, n))
main()


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	a.sort()
	c = 1
	m = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			c = c + 1
		elif c > 1:
			m = m + (c - 1) * c
			c = 1
		if i == n - 1 and c > 1:
			m = m + (c - 1) * c
	print(m)


def process(my_list):
	my_dict = {}
	for item in temp_list:
		my_dict[item] = my_dict.get(item, 0) + 1
	return_sum = 0
	for v in my_dict.values():
		if v > 1:
			return_sum += v * v - v
	print(return_sum)
n = int(input())
for i in range(0, n):
	num_cases = int(input())
	temp_list = []
	temp_list = input().split(' ')
	for j in range(0, len(temp_list)):
		temp_list[j] = int(temp_list[j])
	process(temp_list)


import collections

def pairs(array):
	dic = collections.defaultdict(int)
	for x in array:
		dic[x] += 1
	res = filter(lambda x: x != 1, dic.values())
	count = 0
	for x in res:
		count += x * (x - 1)
	return count
T = int(input())
for _ in range(T):
	N = int(input())
	arr = [int(x) for x in input().split()]
	print(pairs(arr))


import sys

def main():
	T = int(sys.stdin.readline())
	for i in range(0, T):
		N = int(sys.stdin.readline())
		array = map(lambda x: int(x), sys.stdin.readline().split())
		counts = {}
		for elem in array:
			if elem in counts:
				counts[elem] += 1
			else:
				counts[elem] = 1
		sum = 0
		for value in counts.values():
			sum += value * (value - 1)
		print(sum)
main()


from collections import Counter
numCases = int(input().strip())
while numCases:
	numCases -= 1
	arr_size = int(input().strip())
	cdict = Counter(list(map(int, input().strip().split())))
	print(sum((v * (v - 1) for (k, v) in cdict.items())))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for v in a:
		d[v] = d.get(v, 0) + 1
	print(sum((c * (c - 1) for c in d.values())))


import sys

def freopen(f, option, stream):
	import os
	oldf = open(f, option)
	oldfd = oldf.fileno()
	newfd = stream.fileno()
	os.close(newfd)
	os.dup2(oldfd, newfd)
t = int(input())
d = dict()
while t > 0:
	t -= 1
	n = int(input())
	d.clear()
	angka = map(int, input().split())
	for a in angka:
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
	ans = 0
	for key in d.keys():
		temp = d[key]
		ans += temp * (temp - 1)
	print(ans)


for _ in range(int(input())):
	input()
	xs = [int(i) for i in input().split()]
	ys = {}
	s = 0
	for x in xs:
		if x in ys:
			s += ys[x]
			ys[x] += 1
		else:
			ys[x] = 1
	print(2 * s)


def count_equal_pairs(arr, arr_size):
	pairs = 0
	counts = [0 for i in range(0, 1000000)]
	for i in range(0, arr_size):
		counts[arr[i] - 1] += 1
	for c in counts:
		if c > 1:
			pairs += c * (c - 1)
	return pairs

def quicksort_in_place(arr, low, high):
	if low < high:
		p = partition_in_place(arr, low, high)
		quicksort_in_place(arr, low, p - 1)
		quicksort_in_place(arr, p + 1, high)

def partition_in_place(arr, low, high):
	pivotIndex = high
	pivotValue = arr[pivotIndex]
	storeIndex = low
	for i in range(low, high):
		if arr[i] < pivotValue:
			(arr[i], arr[storeIndex]) = (arr[storeIndex], arr[i])
			storeIndex += 1
	(arr[storeIndex], arr[high]) = (arr[high], arr[storeIndex])
	return storeIndex
num_cases = int(input())
for i in range(0, num_cases):
	arr_size = int(input())
	arr = list(map(int, input().split(' ')))
	print(count_equal_pairs(arr, arr_size))


from sys import stdin
t = int(input())
for i in range(0, t):
	n = int(input())
	ar = map(int, input().split())
	dict = {}
	for x in ar:
		if x in dict.keys():
			dict[x] += 1
		else:
			dict[x] = 1
	sum = 0
	for (k, v) in dict.items():
		sum += v * (v - 1)
	print(sum)


import sys
from collections import defaultdict

def histogram(xs):
	histo = defaultdict(lambda : 0)
	for x in xs:
		histo[x] += 1
	return histo

def paircount(xs):
	h = histogram(xs)
	pairs = 0
	done = {}
	for x in xs:
		if not x in done:
			pairs += h[x] * (h[x] - 1)
			done[x] = True
	return pairs
for _ in range(0, int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	xs = [int(x) for x in sys.stdin.readline().strip().split()]
	print(paircount(xs))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	count = [0] * 1000000
	for i in range(n):
		count[a[i] - 1] += 1
	pairs = 0
	for i in range(1000000):
		if count[i] >= 2:
			pairs += count[i] * (count[i] - 1)
	print(pairs)


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	np = 0
	i = 0
	while i < n:
		j = i + 1
		while j < n and a[j] == a[i]:
			j += 1
		d = j - i
		np += d * (d - 1)
		i = j
	print(np)


from math import factorial as fact
for _ in range(int(input())):
	_ = input()
	ocurr = {}
	for i in input().split(' '):
		if i in ocurr:
			ocurr[i] += 1
		else:
			ocurr[i] = 1
	total = sum([int(fact(j) / fact(j - 2)) for (i, j) in ocurr.items() if j > 1])
	print(total)


def get_count(a):
	count = [0] * int(1000000.0 + 1)
	for i in range(len(a)):
		count[a[i]] += 1
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	count = get_count(a)
	pairs = 0
	for item in count:
		pairs += item * (item - 1)
	print(pairs)


__author__ = 'user'
T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	res = 0
	i = 0
	while i < n:
		j = i
		while j < n and a[j] == a[i]:
			j += 1
		res += (j - i) * (j - i - 1)
		i = j
	print(res)


def pairs(x):
	dic = {}
	for i in x:
		if i in dic:
			dic[i] += 1
		elif i not in dic:
			dic[i] = int(1)
	y = 0
	for (key, value) in dic.items():
		if value > 1:
			y += int(value * (value - 1))
	return y
t = int(input())
for i in range(t):
	(m, n) = (int(input()), list(map(int, input().split())))
	ans = pairs(n)
	print(ans)


import array

def qsort(array):
	if not array:
		return []
	else:
		return qsort([i for i in array if i < array[0]]) + [i for i in array if i == array[0]] + qsort([i for i in array if i > array[0]])
t = int(input())
while t > 0:
	n = int(input())
	a = n * [0]
	a = input().split()
	a = qsort(a)
	i = 0
	pairs = 0
	while i < n:
		count = 1
		while i + count < n and a[i + count] == a[i]:
			count += 1
		if count > 1:
			pairs += count * (count - 1)
		if i + count < n:
			i = i + count
		else:
			break
	print(pairs)
	t -= 1


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(_) for _ in input().split()]
	c = Counter(a)
	print(sum([c[i] * (c[i] - 1) for i in c.keys() if c[i] > 1]))


def fun(A):
	myDict = {}
	for num in A:
		if not num in myDict:
			myDict[num] = 1
		else:
			myDict[num] += 1
	res = 0
	for k in myDict:
		v = myDict[k]
		res += v * (v - 1)
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	A = [int(c) for c in input().split()]
	print(fun(A))


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	countA = [0 for x in range(1000001)]
	for num in A:
		countA[num] += 1
	countA = [x for x in countA if x != 0]
	total = 0
	for count in countA:
		total += count * (count - 1)
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	cnt = dict()
	for j in arr:
		if j in cnt:
			cnt[j] += 1
		else:
			cnt[j] = 1
	k = 0
	for j in cnt:
		k += (cnt[j] - 1) * cnt[j]
	print(k)


import collections
n = input()
for i in range(0, int(n)):
	d = collections.defaultdict(int)
	x = input()
	x = int(x)
	y = input()
	y = y.split()
	for j in y:
		d[int(j)] += 1
	s = 0
	for (k, v) in d.items():
		s = s + v * (v - 1) / 2
	print(int(2 * s))
	i += 1


from math import factorial
cases = int(input())

def binomial(n, k):
	return int(factorial(n) / (factorial(k) * factorial(n - k)))
for _ in range(cases):
	n = int(input())
	numbers = map(int, input().split())
	seen = {}
	for number in numbers:
		if number in seen:
			seen[number] = seen[number] + 1
		else:
			seen[number] = 1
	score = 0
	for repetition in seen.values():
		if repetition < 2:
			continue
		else:
			score = score + 2 * binomial(repetition, 2)
	print(score)


from collections import defaultdict
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(c) for c in input().strip().split()]
	S = defaultdict(int)
	for a in A:
		S[a] += 1
	count = 0
	for v in S.values():
		if v > 1:
			count += v * (v - 1)
	print(count)


t = int(input())

def getby2cnt(n):
	ret = 0
	tmp = n - 1
	while tmp > 0:
		ret += tmp
		tmp -= 1
	return ret * 2
for _ in range(0, t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]
	hm = {}
	for i in range(0, n):
		if arr[i] not in hm:
			hm[arr[i]] = [i]
		else:
			hm[arr[i]] += [i]
	ret = 0
	for val in hm.values():
		if len(val) > 1:
			ret += getby2cnt(len(val))
	print(ret)