Jiaozi Pi and Juzi Pi are moving bricks. There are $n$ piles of bricks, where the $i$-th pile contains $a_i$ bricks. The two players take turns moving bricks, with Jiaozi Pi going first.

In the first turn, Jiaozi Pi chooses a pile and removes $s_1$ bricks from it (where $s_1 \ge 1$). In the second turn, Juzi Pi chooses a multiple of $s_1$, denoted as $s_2$ (where $s_2$ can be equal to $s_1$), and removes $s_2$ bricks from any pile. Then, Jiaozi Pi chooses a multiple of $s_2$, denoted as $s_3$, and removes $s_3$ bricks from any pile, and so on. The first player unable to make a move loses.

Jiaozi Pi discovers that he can guarantee a win in many situations. To demonstrate his skill to Juzi Pi, Jiaozi Pi wants you to calculate how many starting moves allow him to guarantee a win. Two starting moves are considered different if and only if Jiaozi Pi removes bricks from a different pile in the first round, or removes a different number of bricks from the same pile.

Input

The first line contains an integer $n$, representing the number of piles.

The second line contains $n$ integers $a_i$, representing the number of bricks in each pile.

Output

Output a single integer representing the number of starting moves that allow Jiaozi Pi to guarantee a win.

Examples

Input 1

1
5

Output 1

3

Note 1

If we denote $(x, y)$ as Jiaozi Pi removing $y$ bricks from the $x$-th pile in his first turn, the starting moves that allow Jiaozi Pi to guarantee a win are $(1, 3), (1, 4), (1, 5)$.

Input 2

7
2 5 10 5 9 9 1

Output 2

13

Constraints

For $50\%$ of the data, $1 \le n \le 100, 1 \le a_i \le 100$.

For $100\%$ of the data, $1 \le n \le 10^6, 1 \le a_i \le 10^6$.

Note

The input size is large; please use fast I/O.