Orange的神奇盒子

题目描述

Orange有一个神奇的盒子，里面包含了 $n$ 个数，Orange定一个神奇数，当且仅当这个数满足他的所有因数都至少在盒子中出现过一次，换句话说我们假设盒子中出现的所有数的集合记作 $A$，神奇数 $x$ 应该满足 $\forall \ d | x$ ，有 $d \in A$。

现在Orange将他的盒子分享给你，你能告诉Orange，自然数中有多少个神奇数吗？

输入格式

输入共2行，第一行为 $n(n \leq 10^6)$，表示Orange盒子中数的个数，第二行包含 $n$ 个整数 $a_i(a_i\leq 10^6)$，为Orange盒子中的数字。

输出格式

一个整数，表示神奇数的个数。

样例 #1

样例输入 #1

7
1 4 3 8 10 8 9

样例输出 #1

3

提示

符合条件的数为$1$，$3$ 和 $9$： $1$ 的因数仅包含$\{1\}$，且被包含在盒子中； $3$ 的因数为$\{1,3\}$，他们都被包含在盒子中； $9$ 的所有因数为 $\{1,3,9\}$，他们都被包含在盒子中。 除了这几个数之外，其他数均不满足条件。