公共因子

题目描述

有 $n$ 个点，第 $i$ 个点的权值为 $a_i$。

对于任意两个不同的点 $i,j$，如果 $\gcd(a_i,a_j)>1$，就在它们之间连一条无向边。

请你求出这张无向图中连通块的数量。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示图中连通块的数量。

样例 1

输入

5
6 10 7 1 15

输出

3

样例 2

输入

6
2 3 5 7 11 13

输出

6

样例说明

在样例 1 中，权值为 $6,10,15$ 的三个点互相直接或间接连通；权值为 $7$ 的点和权值为 $1$ 的点各自形成一个连通块，因此答案为 $3$。

数据范围

对于所有测试数据，保证：