积性函数

时间限制：$1s$

空间限制：$256MB$

题目描述

给定一个序列$A$，满足对任意的$gcd(a,b)=1$，总有$A[a*b]=A[a]*A[b] \%(1e9+7)$。将序列A其中一部分元素替换，得到序列$B$。定义$B$中一个元素$B[i]$是错误的，当且仅当存在若干非错误的$B[p_j]$，使得$i=\prod_{j=0}^{j=k}p_j$且$gcd(p_0,...,p_k)=1$且$B[i]!=(\prod_{j=0}^{j=k}B[p_j])\%(1e9+7)$，你需要给出B中错误元素的个数。

注：下标从 $1$ 开始计算， $i、j、k$ 可以相同。

数据格式

输入

第$1$行$1$个整数，表示元素数量 $n$。

第 $2$ 行$n$个整数，表示序列$B$。保证$B[1]=1$。

输出

输出 $1$ 行，给出B中错误元素的个数。

样例

输入1

10
1 2 32312 12321 5 123124 7 8 9 10

输出1

1

输入2

30
1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 

输出2

0

数据范围及约定

$1≤n≤10^5$。