find-pairs-6

Given an array A of N numbers, find the number of distinct pairs (i, j) such that j ≥i and A[i] = A[j].

First line of the input contains number of test cases T. Each test case has two lines, first line is the number N, followed by a line consisting of N integers which are the elements of array A.

For each test case print the number of distinct pairs.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 10^6 

-10^6 ≤ A[i] ≤ 10^6 for 0 ≤ i < N

SAMPLE INPUT
2
4
1 2 3 4
3
1 2 1

SAMPLE OUTPUT
4
4

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
tc = int(input())
for _ in range(tc):
	size = int(input())
	arr = list(map(int,input().split(" ")))
	arr.sort()
	ans = size
	for i in range(size):
		j = i + 1
		while j < size and arr[j] == arr[i]:
			ans += 1
			j += 1
	print(ans)


tc=int(eval(input()))

while tc:
	cnt = 0
	n = int(eval(input()))
	arr = list(map(int,input().split()))
	for i in range(len(arr)):
		for j in range(i,len(arr)):
			if arr[j]==arr[i]:
				cnt+=1
	print(cnt)
	tc-=1


t = int(input())
for i in range(t):
	n = int(input())
	alist = list(map(int, input().split()))
	c = 0
	l = len(alist)
	for i in range(l):
		for j in range(l):
			if ((alist[i]) == (alist[j]) and (i)<=(j)):
				c = c+1
	print(str(c))			


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
testCases = eval(input())

#print testCases

for i in range(0,testCases):
	arrayLength = eval(input())
	arrayAsString = input()
	arrayList = arrayAsString.split(" ")
	numArray = [int(x) for x in arrayList]
	sortedArray = numArray.sort()
	startIndex=0
	endIndex=0
	resFromDups=0
	while endIndex < arrayLength:
		if numArray[startIndex]!=numArray[endIndex]:
			resFromDups +=((endIndex-startIndex)*(endIndex-startIndex-1))/2
			startIndex=endIndex
		endIndex+=1
	if numArray[startIndex]==numArray[endIndex-1]:
			resFromDups +=((endIndex-startIndex)*(endIndex-startIndex-1))/2		
	print(arrayLength + resFromDups)


t = int(input().strip())
for a0 in range(t):
	n=eval(input())
	a = list(map(int,input().strip().split(' ')))
	count=0
	for i in range(n):
		for j in range(i,n):
			if(a[i]==a[j]):
				count+=1
	print(count)


test = input()

for i in range(0, int(test)):
	n = int(input())
	list1 = input().split(" ")
	elements = [int(x) for x in list1]
	#dup = len(elements) - len(list(set(elements)))
	count = 0
	#print(elements)
	for j in range(0,n):
		for k in range(j,n):
			if(elements[j] == elements[k]):
					count += 1
	print(count)
	#print dup


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc=int(input(""))
for t in range(tc):
	num=int(input(""))
	num_list=input("")
	numlist = [int(x) for x in num_list.split()]

	count=0
	for i in range(num):
		for k in range(num):
			if k < i:
				continue
			if numlist[k] == numlist[i]:
				count += 1
	print(count)



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
testCases = eval(input())

#print testCases

for i in range(0,testCases):
	arrayLength = eval(input())
	arrayAsString = input()
	arrayList = arrayAsString.split(" ")
	numArray = [int(x) for x in arrayList]
	arrayWhenDupsremoved = list(set(numArray))
	#print arrayWhenDupsremoved
	resFromDups =0
	for x in arrayWhenDupsremoved:
		cout = numArray.count(x)
		resFromDups += (cout * (cout-1))/2
	print(arrayLength + resFromDups)


t = int(input())
for test_case in range(t):
	n = input()
	nos = input().split(' ')
	unique = set(nos)
	count = 0
	for no in unique:
		this = nos.count(no)
		no = (this * (this + 1)) / 2
		count += no
	print(count)


for _ in range(eval(input())):
	n = eval(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(len(a)):
		for j in range(i, len(a)):
			if a[i]==a[j]:
				c+=1
	print(c)