find-pairs-2

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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

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


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


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



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


T = int(input())
for i in range(T):
	N = int(input())
	count = N
	x = input().split(' ')
	x = list(map(int,x))
	for j in range(len(x)):
		temp = x[j]
		for k in range(j+1,len(x)):
			if(x[k]==x[j]):
				count+=1
	print(count)
			
	


from collections import Counter
t=eval(input())
while t:
	t-=1
	n=eval(input())
	lst=list(map(int,input().split()))
	c=Counter(lst)
	ans=0
	for k,v in c.most_common(1000000):
		if v!=0 or v!=1:
			ans+=(v)*(v-1)/2
	
	print(ans+n)


def series(x):
	# since for matching 2,2,2,2 count will be 3: and result must be 4C2
	return x*(x+1)/2
 
 
for _ in range(int(input())):
	n = int(input())
	data = [int(i) for i in input().split()]
	data.sort()
	total = 0
	count = 0
	for i in range(1,n):
		if data[i-1] == data[i]:
			count += 1
			if i==n-1:
				total += series(count)
		else:
			total += series(count)
			count = 0
	#data length is added for all i=j
	print((total + len(data)))
			


'''
# 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 tc in range(tc):
	n=int(input())
	count=0
	x=input().split(' ')
	a=list(map(int, x))
	for i in range(n):
		for k in range(i+1,n):
			if a[i]==a[k]:
				count+=1
	print((count+n))			
    			
			
	


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


# your code goes here

	

t= int(eval(input()))
while(t):
	t=t-1
	n=int(eval(input()))
	array=[]
	count=0

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


t=eval(input())
for x in range(0,t):
	n=eval(input())
	case=list(map(int,input().split()))
	cnt=0
	for x in range(0,n):
		for y in range(x,n):
			if case[x]==case[y]:
				cnt+=1
	print(cnt)


t  = int(input())
for tc in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	dic = {i:a.count(i) for i in set(a)}
	ans =0
	for i in dic:
		x = dic[i]
		ans+= x*(x+1)//2
	print(ans)


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


for _ in range(eval(input())):
	n=eval(input())
	lst=input().split()
	ans=0
	x=set(lst)
	for i in x:
		z=lst.count(i)
		ans+=((z+1)*z)/2
	print(ans)	
		


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
data=sys.stdin.readlines()
for i in range(1,len(data),2):
	N=data[i]
	V=data[i+1].split()
	count=len(V)
	for j in range(1,len(V)):
		for k in range(j):
			if V[j]==V[k]:
				count=count+1
	print(count)