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.

Difficulty: interview

Starter code:

Solutions:
3

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 list(cnt.values())]))


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)

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)

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)

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 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()


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 list(d.values()):
        result += i * (i - 1) // 2
    
    print(result)

main()



def helper(x):
    res = 0
    while x > 0 :
        if x % 2 == 0: x //= 2
        else:
            res+=1
            x //= 2
    return res


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

for element in a:
    res = helper(element)
    if d.__contains__(res):
        d[res]+=1
    else:
        d[res] = 1

ans = 0
for element in d:
    ans += d[element]*(d[element]-1)/2

print(int(ans))




def helper(x):
    res = 0
    while x > 0 :
        if x % 2 == 0: x //= 2
        else:
            res+=1
            x //= 2
    return res


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

for element in a:
    res = helper(element)
    d[res] = d.get(res, 0)+1

ans = 0
for element in d:
    ans += d[element]*(d[element]-1)/2

print(int(ans))




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))



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))

import array
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))



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))

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)


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())

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))



 



# Made By Mostafa_Khaled


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

#print( cnt )

ans = 0
for i in cnt:
    ans += int( cnt[i] * ( cnt[i] - 1 ) / 2 )

print( ans )


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())
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))


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)

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)

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)




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))











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
#print(ans)
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)