该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在遥远的数理王国中，流传着“素源封印”的古老仪式。

王国中散落着 $n$ 块蕴含不同频率的符晶，第 $i$ 个编号为 $a_i$。据传，若将符晶随意堆置，频率共振会引发灾难；唯有将它们分门别类，按照“共振和谐”的原则排列，方能将其能量安稳封印。

• 对任意两块符晶 $i$ 与 $j$，定义它们的共振强度为：$$\gcd(a_i,a_j)$$
• 若两块符晶的共振强度大于 $1$，则它们会产生不稳定谐振；只有当 $\gcd(a_i,a_j) = 1$ 时，这对符晶才能在同一阵列中和谐共存。

题目描述

国王下旨：

“诸贤将此 $n$ 块符晶，按照安全共存之道，分置于若干封印阵列中，以镇压其潜在能量。务必使得每个阵列内的任意两块符晶均满足 $\gcd(a_i,a_j)=1$。问：最少需要多少个封印阵列，方可完成此殊胜之举？”

输入格式

第一个 $1$ 个正整数 $n$，表示有 $n$ 块符晶。

第二行 $n$ 个正整数 $a_i$。

输出格式

一个整数，表示至少需要的封印阵列数。

样例输入输出

样例 1

输入

5
1241 539 5860 8034 8231

输出

2

数据范围与提示

• $1 \le n \le 10$
• $1 \le a_i \le 10^4$