Nim Game 3

Interview

Time limit1sMemory limit512 MB

Summary

Given Nim pile sizes, count how many first moves (choosing a pile and removing stones) leave the opponent in a losing position.

Level: Medium5 of 10
Topics: Game theory, Bit manipulation, Math, Greedy
Solved: No attempts yet

Problem

Gusagwa and CubeLover are playing a game of Nim. Nim uses $k$ piles of stones stacked upward, and each pile contains at least one stone. The two players take turns. On your turn, you choose one pile that has stones and remove one or more stones from that pile. The player who removes the last stone from all piles wins.

Gusagwa moves first. Assuming both players play optimally, find the number of moves Gusagwa can make on the first turn that let him win the game.

Input

The first line gives the number of stone piles $N$ ( $1 \le N \le 1000$ ).

The second line gives the number of stones $P_i$ in each pile ( $1 \le P_i \le 1000$ ).

Output

Print the number of moves Gusagwa can make on the first turn that let him win the game.

Examples5

Example 1
Input
```
3
11 15 8
```
Expected output
```
3
```
Example 2
Input
```
3
11 15 7
```
Expected output
```
3
```
Example 3
Input
```
3
2 3 4
```
Expected output
```
1
```
Example 4
Input
```
3
1 2 3
```
Expected output
```
0
```
Example 5
Input
```
5
99 66 33 98 55
```
Expected output
```
3
```