A君有一个集合。
这个集合有个神奇的性质。
若X,Y属于该集合，那么X与Y的最大公因数也属于该集合。
但是他忘了这个集合中原先有哪些数字。
不过幸运的是，他记起了其中n个数字。
当然，或许会因为过度紧张，他记起来的数字可能会重复。
他想还原原先的集合。
他知道这是不可能的……
现在他想知道的是，原先这个集合中至少存在多少数。
样例解释：
该集合中一定存在的是{1,2,3,4,6}
Input
第一行一个数n(1<=n<=100000)。
第二行n个数，ai(1<=ai<=1000000，1<=i<=n)。表示A君记起来的数字。
输入的数字可能重复。
Output
输出一行表示至少存在多少种不同的数字。
Input示例
5
1 3 4 6 6
Output示例
5
/*
自己还是太弱了……
因为正着考虑一定会超时，随意考虑反着做，即枚举数字，看它是否属于这个集合（其实这点我想到了）。
检验的方法很巧妙：看这个数在原集合中出现的倍数的gcd是否等于这个数，如果相等，则该数也属于集合。
*/
#include<cstdio>
#include<iostream>
#define N 1000010
using namespace std;
int a[N],used[N],n;
int gcd(int x,int y){
if(!y)return x;
return gcd(y,x%y);
}
int main(){
scanf("%d",&n);int p=,m=;
for(int i=;i<=n;i++){
int x;scanf("%d",&x);
if(!used[x]){
a[++p]=x;
used[x]=;
m=max(m,x);
}
}
n=p;
for(int i=;i<=m;i++){
if(used[i])continue;
int w=;
for(int j=i;j<=m;j+=i){
if(used[j])w=gcd(w,j);
}
if(w==i)p++;
}
printf("%d",p);
return ;
}