the-savior-3

Fatal Eagle is trying his best to save his city, but he's failing to do so. He knows he needs some external help; some guidance, something... something out of ordinary to defeat this powerful enemy called Mr. XYZ.
"Find out the number of pairs in the list you've made, who sum up to
an even number!"

"Who are you? And what do you mean? Can you elaborate a bit?"  Exclaims Fatal Eagle.

"I meant, what I said... take a look at the sample explanation of the
problem I want you to solve, you'll understand perhaps. And as for who
I am? I'm Arjit and like you, I just want to save this city, too."
Fatal Eagle is quick to respond to Arjit's task, and decides to solve it quickly. He takes out the list of integers which contains the powers of weird creatures, and starts finding out the number of pairs which sum up to an even number. Here's how he does it:

Let's say that he had a list of 4 numbers: [1, 2, 3, 4]
His answer would be: 2. How? 1+3 = 4 and 2 + 4 - that is to say, a number will NOT be added to itself and 1+3 is same as 3+1.

Input format:
On the first line of the input there is an integer, T, which denotes the number of test cases. For every test case, there is a number N, denoting the size of the list. Then, on the next line there are N numbers denoting the integers in the list.

Output format:
You need to output the number of required pairs.

Constraints:
1 ≤ Test Cases ≤ 50
1 ≤ Number of elements ≤ 10^3
1 ≤ Value of the elements - Ni ≤ 10^5

SAMPLE INPUT
4
2
1 1
4
1 2 3 4
4
2 4 6 8
3
1 3 3

SAMPLE OUTPUT
0
2
6
2

Explanation

In the first case, since the numbers are same, they will not be considered. 
The second case is explained in the question itself.
In the third case, 6 pairs are: (2, 4) (2, 6) (2, 8) (4, 6) (4, 8) (6, 8).
In the fourth case, 2 pairs are: (1, with the 1st 3) (1, with the 2nd 3).

Source: hackerearth | Difficulty: EASY
Tags: Mathematics

Ad-hoc


Solutions:
t=int(input())
while(t):
	n=int(input())
	a=list(map(int,input().split()))
	count=0
	for i in range(n):
		for j in range(i+1,n):
			if (a[i]+a[j])%2==0 and a[i]!=a[j]:
				count+=1
	print(count)
	t-=1


from itertools import combinations

t = int(input())
for te in range(1,t+1):
	siz = int(input())
	lis = list(map(int,input().split()))
	count = 0
	for mylist in combinations(lis,2):
		if(mylist[0]!=mylist[1]):
			if(sum(mylist)%2==0):
				count+=1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	tot = 0
	for j in range(len(l)):
		for y in range(j+1, len(l)):
			if l[j] != l[y] and (l[j] + l[y]) % 2 == 0:
				tot += 1
	print(tot)


for _ in range(eval(input())):
	nos = eval(input())
	ins = list(map(int, input().split()))
	cnt = 0
	for i in range(len(ins)-1):
		for j in range(i+1, len(ins)):
			if (ins[i] + ins[j]) & 1 == 0 and ins[i] != ins[j]:
				cnt += 1
				
	print(cnt)            
				


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=int(input())
while(t):
	n=int(input())
	a=list(map(int,input().split()))
	count=0
	for i in range(n):
		for j in range(i+1,n):
			if (a[i]+a[j])%2==0 and a[i]!=a[j]:
				count+=1
	print(count)
	t-=1
				
	


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from collections import Counter
T=eval(input())
for t in range(T):
	N=eval(input())
	x=[int(x) for x in input().split()]
	even=[]
	odd=[]
	eve=0
	od=0
	final=set()
	i=0
	for i in x:
		if(i%2==0):
			even+=[i]
		else:
			odd+=[i]
	count=0        
	even=dict(Counter(even))
	#print even
	if(len(even)!=0):
		sum1=sum(even.values())
		for i in even:
			count+=even[i]*(sum1-even[i])
			sum1=sum1-even[i]
	odd=dict(Counter(odd))
	#print even
	if(len(odd)!=0):
		sum1=sum(odd.values())
		for i in odd:
			count+=odd[i]*(sum1-odd[i])
			sum1=sum1-odd[i]
	print(count)


t=int(input())
i=0
while i<t:
	n=int(input())
	a=[int(x) for x in input().split()]
	b=[]
	c=[]
	for j in range(len(a)):
		if a[j]%2==0:
			b.append(a[j])
		else:
			c.append(a[j])
	c.sort()
	b.sort()
	sumi=0
	for k in range(len(b)-1):
		sumi+=len(b[k:])-(b[k:].count(b[k]))
	for k in range(len(c)-1):
		sumi+=len(c[k:])-(c[k:].count(c[k]))
	print(sumi)

	i+=1


for i in range(int(input())):
	x = int(input())
	y = list(map(int, input().split(' ')))
	t=0
	for a in y:
		for b in y:
			if a != b and (a+b)%2==0:
				t+=1
	print((t//2))


from itertools import combinations
T=int(input())
for t in range (0,T):
	n=int(input())
	a=[]
	a = [int(z) for z in input().split()]
	c=0
	for j in combinations(a,2):
		
		if sum(j)%2==0 and j[0]!=j[1]:
			c=c+1
	print(c)
	


t=int(input())
while(t):
	n=int(input())
	a=list(map(int,input().split()))
	count=0
	for i in range(n):
		for j in range(i+1,n):
			if (a[i]+a[j])%2==0 and a[i]!=a[j]:
				count+=1
	print(count)
	t-=1
			
				
   
	


tc = int(input())
while tc>0:
	tc = tc - 1
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(n):
			if l[i]==l[j]:
				pass
			else:
				if (l[i]+l[j])%2==0:
					ans = ans + 1
	print(ans/2)



testcount = int(input())
anslist = []
for i in range(0,testcount):
	listlen = int(input())
	itemlist = input().split()[0:listlen]
	itemlist = [int(l) for l in itemlist]
	count = 0
	for j in range(0,len(itemlist)):
		for k in itemlist[j+1:]:
			if (itemlist[j] != k) and ((itemlist[j]+k)%2 == 0):
				count += 1
	anslist.append(count)
for i in anslist:
	print(i)


t = eval(input())
for _ in range(t):
	n = eval(input())
	num = [int(i) for i in input().split()]
	ev = 0
	od = 0
	mx=(10**5)+1
	hs=[0]*(mx)
	for i in num:
		if(i%2==0):
			ev+=1
		else:
			od+=1
		hs[i]+=1
	now = 0
	num = list(set(num))
	for i in num:
		if(i%2==0):
			now+=hs[i]*(ev-hs[i])
		else:
			now+=hs[i]*(od-hs[i])
	print(now>>1)


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def GetCount(l):
	if (len(l)==1):
		return 0
	n_l = l[:-1]
	b_l = [i%2==0 for i in l]
	index=0
	totalCount=0
	for element in n_l:
		current_even = element%2==0
		totalCount += b_l[index+1:].count(current_even)
		totalCount -= l[index+1:].count(element)
		index += 1
	return totalCount

testCase = int(input())
while(testCase):
	n = int(input())
	l = [int(i) for i in input().split()]
	print((GetCount(l)))
	testCase-=1


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=int(input())
while(t):
	n=int(input())
	a=list(map(int,input().split()))
	count=0
	for i in range(n):
		for j in range(i+1,n):
			if (a[i]+a[j])%2==0 and a[i]!=a[j]:
				count+=1
	print(count)
	t-=1
				
	


tc = int(input())
for i in range(tc):
	n = int(input());
	inp = list(map(int,input().split()));
	cnt=0;
	for j in range(n):
		a = inp[j];
		for k in range(j+1,n):
			b = inp[k];
			if(a!=b and (a+b)%2==0):
				cnt+=1;
	print(cnt);			


t = int(input())
while t:
	n = int(input())
	l = list(map(int,input().split()))
	c = 0
	h = []
	for i in range(0,n-1):
		k = i+1
		for j in range(k,n):
			v = l[i]+l[j]
			if (v % 2 == 0) and (l[i] != l[j]):
				c += 1
	print(c)
	t -= 1
	


t = int(input());
for k in range(1,t+1):
	n = int(eval(input()));
	a = [int(x) for x in input().split()]
	count = 0
	for i in range(n):
		for j in range(i+1,n):
			if a[i] != a[j]:
				if ((a[i]%2)==0 and (a[j]%2)==0):
					count += 1;
				elif ((a[i]%2)!=0 and (a[j]%2)!=0):
					count += 1;
				else :
					pass
	print(count)