Stone Game

문제

Bessie and Elsie are playing a game with $NN$ ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$) piles of stones, where the $ii$-th pile has $a_{i}a\_i$ stones for each $1\le i\le N1\backslash le\; i\backslash le\; N$ ($1\le a_i\le {10}^{6}1\backslash le\; a\_i\backslash le\; 10^6$). The two cows alternate turns, with Bessie going first.

• First, Bessie chooses some positive integer $s_{1}s\_1$ and removes $s_{1}s\_1$ stones from some pile with at least $s_{1}s\_1$ stones.
• Then Elsie chooses some positive integer $s_{2}s\_2$ such that $s_{1}s\_1$ divides $s_{2}s\_2$ and removes $s_{2}s\_2$ stones from some pile with at least $s_{2}s\_2$ stones.
• Then Bessie chooses some positive integer $s_{3}s\_3$ such that $s_{2}s\_2$ divides $s_{3}s\_3$ and removes $s_{3}s\_3$ stones from some pile with at least $s_{3}s\_3$ stones and so on.
• In general, $s_{i}s\_i$, the number of stones removed on turn $ii$, must divide $s_{i+1}s\_\{i+1\}$.

The first cow who is unable to remove stones on her turn loses.

Compute the number of ways Bessie can remove stones on her first turn in order to guarantee a win (meaning that there exists a strategy such that Bessie wins regardless of what choices Elsie makes). Two ways of removing stones are considered to be different if they remove a different number of stones or they remove stones from different piles.

입력

The first line contains $NN$.

The second line contains $NN$ space-separated integers $a_1,\dots ,a_{N}a\_1,\backslash ldots,a\_N$.

출력

Print the number of ways Bessie can remove stones on her first turn in order to guarantee a win.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

1
7

4

6
3 2 3 2 3 1

8