Total Set Bits

Statement

You are given n non-negative integers. Write each one in binary and count its 1 bits. Print the total number of 1 bits over all the numbers.

Input

The first line has n. The second line has the n integers.

Output

Print one integer: the total number of 1 bits.

Constraints

1 <= n <= 200000
0 <= a_i <= 10^18

Example 1

3
1 2 3

4

1 is 1, 2 is 10 and 3 is 11 in binary: 1 + 1 + 2 = 4 ones.

Example 2

2
255 256

9

255 is 11111111 (eight ones) and 256 is 100000000 (one one).