find-pairs-7

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:
for _ in range(eval(input())):
	f = [0] * 2222222
	add = 1111111
	n = eval(input())
	ans = 0
	m = list(map(int, input().split()))
	for i in range(n):
		f[m[i]+add]+=1
		ans += f[m[i]+add]
	print(ans)    


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=eval(input())
for _ in range(t):
	n=eval(input())
	a=list(map(int, input().split()))
	d=dict()
	for x in a:
		if not x in d: d[x]=1
		else: d[x]+=1
	tot=0
	for v in list(d.values()):

			tot+=v*(v-1)/2+v
	print(tot)	


'''
# Read input from stdin and provide input before running code
 
name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def pairs(lis,l):
	c=0
	i=0
	while i<l :
		j=i
		while j<l and j>=i:
			if lis[i] == lis[j]:
				c =c+1
			j=j+1
		i=i+1
	return c
	
	
t= eval(input())
re=[]
for i in range(t):
	l=eval(input())
	s=input()
	s=s.split()
	re.append(pairs(s,l))
	
for i in re:
	print(i)


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


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


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