题目描述

饺子皮和橘子皮在搬砖。一共有 $n$ 堆砖需要运走，第 $i$ 堆有 $a_i$ 块。两个人比赛轮流搬砖，饺子皮先搬。

饺子皮首先会随便选择一堆砖搬走其中的 $s_1$ 块（至少搬一块）；橘子皮会选择 $s_1$ 的倍数 $s_2$（可以相等），然后从某一堆中搬走 $s_2$ 块；然后饺子皮会选择 $s_2$ 的倍数 $s_3$，然后从某一堆中搬走 $s_3$ 块，以此类推。最先无法操作的人输。

饺子皮发现，在好多种情况下自己都能稳赢橘子皮。为了更好地向橘子皮展示自己的实力，饺子皮希望你帮他算一算有多少种开局方式能让饺子皮稳赢。两种开局方式不同，当且仅当饺子皮在第一轮搬走了不同堆中的砖，或者在同一堆砖中搬走了不同数量的砖。

输入格式

从标准输入读入数据。

输入的第一行一个整数 $n$ 表示堆数；

第二行 $n$ 个整数 $a_i$ 表示每一堆的砖数。

输出格式

输出到标准输出。

一行一个整数，表示能让饺子皮稳赢的开局方式数量。

样例

输入

1
5

输出

3

解释

如果使用 $(x,y)$ 表示饺子皮第一次从第 $x$ 堆中取走 $y$ 块砖，那么能让饺子皮稳赢的开局方式有 $(1,3),(1,4),(1,5)$。

样例

输入

7
2 5 10 5 9 9 1

输出

13

样例三

见下载目录下的 ex_3.in 与 ex_3.ans。

数据范围

对于 $50\%$ 的数据，$1 \le n \le 100, 1 \le a_i \le 100$。

对于 $100\%$ 的数据，$1 \le n \le 10^6, 1 \le a_i \le 10^6$。

提示

输入量较大，请注意读入优化。