题目描述

Bessie 和 Elsie 正在用 $N$（$1\le N\le 10^5$）堆石子进行一个游戏，其中对于每个 $1\le i\le N$，第 $i$ 堆石子有 $a_i$ 个石子（$1\le a_i\le 10^6$）。两头奶牛交替行动，Bessie 先手。

• 首先，Bessie 选择某个正整数 $s_1$ 并从至少包含 $s_1$ 个石子的某堆石子中取走 $s_1$ 个石子。
• 然后 Elsie 选择某个正整数 $s_2$，使得 $s_1$ 整除 $s_2$，并从至少包含 $s_2$ 个石子的某堆石子中取走 $s_2$ 个石子。
• 然后 Bessie 选择某个正整数 $s_3$，使得 $s_2$ 整除 $s_3$，并从至少包含 $s_3$ 个石子的某堆石子中取走 $s_3$ 个石子，以此类推。
• 总的来说，第 $i$ 回合中取走的石子数量 $s_i$ 必须整除 $s_{i+1}$。

第一个无法在其回合中取走石子的奶牛为失败者。

计算可以令 Bessie 必胜（表示存在一种策略，无论 Elsie 如何行动，Bessie 均可获胜）的第一回合取石子的方法数。如果两种取石子的方法中取的石子数量不同或者取的石子堆不同，则认为是两种不同的取石子的方法。

输入格式

输入的第一行包含 $N$。

第二行包含 $N$ 个空格分隔的整数 $a_1,\ldots,a_N$。

输出格式

输出可以令 Bessie 必胜（表示存在一种策略，无论 Elsie 如何行动，Bessie 均可获胜）的第一回合取石子的方法数。

注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储（例如，C/C++ 中的 long long）。

1
7

4

6
3 2 3 2 3 1

8

提示

样例 1 解释：

当 Bessie 从唯一的一堆石子中取走 $4$、$5$、$6$ 或 $7$ 个石子时可以获胜。此时游戏会立刻结束。

样例 2 解释：

当 Bessie 从任意一堆中取走 $2$ 或 $3$ 个石子时可以获胜。此后两头奶牛会交替取走相同数量的石子，而 Bessie 执行了最后一次操作。

测试点性质：

• 对于另外 $15\%$ 的数据，满足 $N=2$。
• 对于另外 $25\%$ 的数据，满足 $N,a_i\le 100$。
• 对于另外 $50\%$ 的数据，没有额外限制。

供题：Benjamin Qi