Dima got into number sequences. Now he's got sequence a_1, a_2, ..., a_{n}, consisting of n positive integers. Also, Dima has got a function f(x), which can be defined with the following recurrence:  f(0) = 0;  f(2·x) = f(x);  f(2·x + 1) = f(x) + 1. 

Dima wonders, how many pairs of indexes (i, j) (1 ≤ i < j ≤ n) are there, such that f(a_{i}) = f(a_{j}). Help him, count the number of such pairs. 


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).

The numbers in the lines are separated by single spaces.


-----Output-----

In a single line print the answer to the problem.

Please, don't use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
3
1 2 4

Output
3

Input
3
5 3 1

Output
1



-----Note-----

In the first sample any pair (i, j) will do, so the answer is 3.

In the second sample only pair (1, 2) will do.

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Implementation


Solutions:
def helper(x):
	ret = 0
	while x > 0:
		if x % 2 == 0:
			x //= 2
		else:
			ret += 1
			x //= 2
	return ret
n = int(input())
a = list(map(int, input().split()))
d = [0] * 10000
for element in a:
	res = helper(element)
	d[res] += 1
ans = 0
for element in d:
	ans += element * (element - 1) / 2
print(int(ans))


n = int(input())
x = [bin(int(i)).count('1') for i in input().split()]
s = 0
for i in range(max(x) + 1):
	s = s + x.count(i) * (x.count(i) - 1)
print(int(s / 2))


input()
res = [0] * 10 ** 5
ans = 0
a = list(map(int, input().split()))
for i in a:
	res[bin(i).count('1')] += 1
for i in range(10 ** 5):
	ans += res[i] * (res[i] - 1) // 2
print(ans)


def num(x):
	return bin(x).count('1')

def main():
	n = int(input())
	line = list(map(int, input().split()))
	cou = dict()
	for i in range(n):
		new = num(line[i])
		if new not in cou:
			cou[new] = 0
		cou[new] += 1
	ans = 0
	for el in cou:
		ans += cou[el] * (cou[el] - 1) // 2
	print(ans)
main()


n = int(input())
t = list(map(int, input().split()))
(p, s) = ({}, 0)
for i in t:
	j = sum((k == '1' for k in format(i, 'b')))
	p[j] = p.get(j, 0) + 1
for j in p:
	s += p[j] * (p[j] - 1)
print(s // 2)


n = int(input())
a = list(map(int, input().split()))

def f(n):
	return sum([1 for i in n if i == '1'])
cnt = {}
for i in range(n):
	tmp = f(bin(a[i])[2:])
	if tmp not in cnt:
		cnt[tmp] = 1
	else:
		cnt[tmp] += 1
ans = 0
for i in cnt:
	ans += int(cnt[i] * (cnt[i] - 1) / 2)
print(ans)


n = int(input())
p = [int(x) for x in input().split()]
for i in range(0, n):
	p[i] = str(bin(p[i])).count('1')
s = set(p)
t = 0
for j in s:
	t += p.count(j) * (p.count(j) - 1) / 2
print(int(t))


def main():

	def f(x):
		if x < L:
			return prec[x]
		return f(x // 2) + x % 2
	n = int(input())
	a = [int(i) for i in input().split()]
	L = 10 ** 5
	prec = [0]
	for i in range(1, L):
		if i % 2 == 1:
			prec.append(prec[i - 1] + 1)
		else:
			prec.append(prec[i // 2])
	d = {}
	for i in a:
		value = f(i)
		if value not in d:
			d[value] = 0
		d[value] += 1
	result = 0
	for i in list(d.values()):
		result += i * (i - 1) // 2
	print(result)
main()


import sys
import math
from collections import defaultdict

def count_set_bits(n):
	res = 0
	while n:
		res += n & 1
		n >>= 1
	return res

def solve(test):
	n = int(input())
	a = list(map(int, input().split()))
	rec = defaultdict(int)
	for i in range(n):
		rec[count_set_bits(a[i])] += 1
	ans = 0
	for i in rec:
		ans += rec[i] * (rec[i] - 1) // 2
	print(ans)
test_cases = 1
for t in range(1, test_cases + 1):
	solve(t)


from collections import defaultdict
(p, n) = (defaultdict(int), int(input()))
for i in map(int, input().split()):
	p[bin(i).count('1')] += 1
print(sum((x * (x - 1) for x in p.values())) // 2)


def C(x):
	s = bin(x)[2:]
	c = 0
	for t in s:
		if t == '1':
			c += 1
	return c
n = input()
ar = list(map(int, input().split()))
bu = {}
for e in ar:
	c = C(e)
	if c not in bu:
		bu[c] = 0
	bu[c] += 1
S = 0
for v in list(bu.values()):
	S += v * (v - 1) // 2
print(S)


n = int(input())
a = list(map(int, input().split()))

def f(x):
	cnt = 0
	while True:
		if x == 1:
			cnt += 1
			break
		elif x % 2 == 1:
			cnt += 1
			x = (x - 1) / 2
		else:
			x = x / 2
	return cnt
my_dict = {}
for i in range(n):
	d = f(a[i])
	if d in my_dict.keys():
		my_dict[d] += 1
	else:
		my_dict[d] = 1
result = 0
for key in my_dict.keys():
	t = my_dict[key]
	result += int(t * (t - 1) / 2)
print(result)


import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right, bisect
popcount = [0] * 32
n = int(input())
a = list(map(int, stdin.readline().split()))
for i in a:
	temp = 0
	for j in range(31):
		if i & 1 << j:
			temp += 1
	popcount[temp] += 1
ans = 0
for i in popcount:
	if i > 1:
		ans += i * (i - 1) // 2
print(ans)


def main():
	from collections import defaultdict

	def f(x):
		if x < L:
			return prec[x]
		return f(x // 2) + x % 2
	n = int(input())
	a = [int(i) for i in input().split()]
	L = 10 ** 5
	prec = [0]
	for i in range(1, L):
		if i % 2 == 1:
			prec.append(prec[i - 1] + 1)
		else:
			prec.append(prec[i // 2])
	d = defaultdict(int)
	for i in a:
		d[f(i)] += 1
	result = 0
	for i in d.values():
		result += i * (i - 1) // 2
	print(result)
main()


n = int(input())
l = [int(i) for i in input().split()]

def cnt(n):
	c = 0
	while n:
		if n & 1:
			c = c + 1
		n = n // 2
	return c
bits = [0] * 40
for i in l:
	bits[cnt(i)] += 1
ans = 0
for i in range(40):
	ans = ans + bits[i] * (bits[i] - 1) // 2
print(ans)


n = int(input())
a = list(map(int, input().split()))
d = dict()
for e in a:
	c = bin(e).count('1')
	d[c] = d.get(c, 0) + 1
print(sum((v * (v - 1) // 2 for v in d.values())))


def f(x):
	return str(bin(x)).count('1')
n = int(input())
a = list(map(int, input().split()))
ans = [f(x) for x in a]
s = set(ans)
counts = {x: ans.count(x) for x in s}
ans = 0
for i in counts:
	ans += counts[i] * (counts[i] - 1) // 2
print(ans)


mem = [-1] * 100000

def f(x):
	if x == 0:
		return 0
	if x < 100000 and mem[x] != -1:
		return mem[x]
	if x % 2 == 0:
		res = f(x // 2)
	else:
		res = f((x - 1) // 2) + 1
	if x < 100000:
		mem[x] = res
	return res
n = int(input())
a = list(map(int, input().split()))
cnt = {}
for v in a:
	k = f(v)
	cnt[k] = cnt.get(k, 0) + 1
print(sum([v * (v - 1) // 2 for v in cnt.values()]))


from sys import stdin, stdout
from bisect import bisect_right as br
from bisect import bisect_left as bl
from bisect import insort_left as il
from math import gcd

def cho(n):
	return n * (n - 1) // 2

def val(n):
	ans = 0
	while n:
		if n & 1:
			ans += 1
		n //= 2
	return ans
n = int(stdin.readline())
lst = [int(i) for i in stdin.readline().split()]
lst2 = []
for i in lst:
	lst2 += [val(i)]
lst2.sort()
temp = lst2[0]
c = [1]
ans = 0
for i in lst2[1:]:
	if i == temp:
		c[-1] += 1
	else:
		c += [1]
	temp = i
for i in c:
	ans += cho(i)
stdout.write(str(ans))


y = []
a = int(input())
x = list(map(int, input().split()))
for i in x:
	y.append(bin(i).count('1'))
y.sort()
t = 0
if a == 1:
	print(0)
else:
	streak = 1
	for i in range(1, a):
		if y[i] == y[i - 1]:
			streak += 1
		else:
			t += streak * (streak - 1) / 2
			streak = 1
	t += streak * (streak - 1) / 2
	print(int(t))


n = int(input())
lis = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
	k = lis[i]
	c = 0
	while k > 0:
		if k % 2 != 0:
			c += 1
		k = k // 2
	ans[i] = c
ans.sort()
c = 1
fin = 0
for i in range(1, n):
	if ans[i - 1] == ans[i]:
		c += 1
	else:
		fin += c * (c - 1) // 2
		c = 1
fin += c * (c - 1) // 2
print(fin)


n = int(input())

def f(a):
	if a == 0:
		return 0
	else:
		return f(norm(a) - 1) + 1

def norm(a):
	if a > 0 and a % 2 == 0:
		while a % 2 == 0:
			a //= 2
	if a > 1:
		while (a - 1) % 4 == 0:
			a = (a - 1) // 2 + 1
	return a
m = sorted([f(int(x)) for x in input().split()])
s = 0
w = 0
for i in range(len(m) - 1):
	if m[i] == m[i + 1]:
		w += 1
	else:
		s += w * (w + 1) // 2
		w = 0
s += w * (w + 1) // 2
print(s)


(p, n) = ({}, int(input()))
t = list(map(int, input().split()))
for i in t:
	j = format(i, 'b').count('1')
	p[j] = p.get(j, 0) + 1
print(sum((x * (x - 1) for x in p.values())) // 2)


n = int(input())
arr = list(map(int, input().split()))
d = {}
for i in arr:
	c = bin(i).count('1')
	d[c] = d.get(c, 0) + 1
res = [v * (v - 1) // 2 for v in list(d.values())]
print(sum(res))


def rec(x):
	if x == 1:
		return 1
	if x % 2 == 0:
		return rec(x // 2)
	else:
		return rec(x // 2) + 1
n = int(input())
l = list(map(int, input().split()))
d = {}
ans = 0
for i in l:
	som = rec(i)
	if som in d:
		d[som] += 1
	else:
		d[som] = 1
for i in d:
	ans = ans + int((d[i] - 1) / 2 * d[i])
print(ans)