Nim

Limits: 2 sec., 256 MiB

Zenyk and Marichka play one well-known game. They have \(N\) piles of stones, \(i\)-th pile contains \(A_i\) stones. It’s known that Marichka can win only if xor of all piles’ sizes equals 0.

Marichka decides to cheat and add some stones to some of the piles. Find the minimum number of stones Marichka should add so that she can win this game. Note that Marichka can’t create new piles or rearrange stones in existing piles.

xor is a logical operation that outputs true only when inputs differ. To find xor of two numbers \(a\) and \(b\) you should find binary representation of both numbers and compute sum of each bit modulo 2 separately.

Input

The first line contains one integer \(N\). The second line contains \(N\) integers \(A_i\).

Output

Print the minimum number of stones Marichka has to add.

Constraints

\(2 \le N \le 1000\),

\(0 \le A_i \le 10^9\).

Samples