Description

Bessie and Elsie are playing a game with $N$ ($1 \le N \le 10^5$) piles of stones. For each $1 \le i \le N$, the $i$-th pile contains $a_i$ stones ($1 \le a_i \le 10^6$). The two cows take turns, and Bessie moves first.

• First, Bessie chooses a positive integer $s_1$ and removes $s_1$ stones from some pile that has at least $s_1$ stones.
• Then Elsie chooses a positive integer $s_2$ such that $s_1$ divides $s_2$, and removes $s_2$ stones from some pile that has at least $s_2$ stones.
• Then Bessie chooses a positive integer $s_3$ such that $s_2$ divides $s_3$, and removes $s_3$ stones from some pile that has at least $s_3$ stones, and so on.
• In general, the number of stones removed on turn $i$, $s_i$, must divide $s_{i+1}$.

The first cow who cannot remove stones on her turn loses.

Compute the number of possible first moves that guarantee Bessie a win (meaning there exists a strategy such that no matter how Elsie plays, Bessie will win). Two first moves are considered different if either the number of stones removed is different, or the pile chosen is different.

Input Format

The first line contains $N$.

The second line contains $N$ space-separated integers $a_1,\ldots,a_N$.

Output Format

Output the number of first moves that guarantee Bessie a win (meaning there exists a strategy such that no matter how Elsie plays, Bessie will win).

Note that the integer sizes in this problem may require using 64-bit integers (for example, long long in C/C++).

1
7

4

6
3 2 3 2 3 1

8

Hint

Explanation for Sample 1:

Bessie can win if she removes $4$, $5$, $6$, or $7$ stones from the only pile. In this case, the game ends immediately.

Explanation for Sample 2:

Bessie can win if she removes $2$ or $3$ stones from any pile. After that, the two cows will alternate removing the same number of stones, and Bessie makes the last move.

Test Point Properties:

• For an additional $15\%$ of the testdata, $N=2$.
• For an additional $25\%$ of the testdata, $N,a_i \le 100$.
• For an additional $50\%$ of the testdata, there are no additional constraints.

Problem by: Benjamin Qi.

Translated by ChatGPT 5