给定一个整数序列 $$$a_1, a_2, \dots, a_n$$$。您需要用颜色绘制元素,以便:
- 如果我们考虑任何颜色,该颜色的所有元素都必须能被该颜色的最小元素整除。
- 必须尽量减少使用的颜色数量。
例如,可以用单一颜色绘制元素 $$$[40, 10, 60]$$$,因为它们都可以被 $$$10$$$ 整除。您可以任意次数地使用任何颜色(特别是,只允许使用一种颜色一次)。用一种颜色绘制的元素不需要是连续的。
例如,如果 $$$a=[6, 2, 3, 4, 12]$$$ 则需要两种颜色:让我们用第一种颜色绘制 $$$6$$$、$$$3$$$ 和 $$$12$$$($$$6$$$、$$$3$$$ 和 $$$12$$$ 可以被 $$$3$$$ 整除)并绘制$$$2$$$ 和 $$$4$$$ 为第二种颜色($$$2$$$ 和 $$$4$$$ 可被 $$$2$$$ 整除)。例如,如果 $$$a=[10, 7, 15]$$$ 则需要 $$$3$$$ 颜色(我们可以简单地将每个元素绘制为唯一的颜色)。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$),其中 $$$n$$$ 是给定序列的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$)。这些数字可以包含重复项。
输出
打印最少数量的颜色,以有效的方式绘制所有给定的数字。
示例
输入 #1
6 10 2 3 5 4 2
输出 #1
3
输入 #2
4 100 100 100 100
输出 #2
1
输入 #3
8 7 6 5 4 3 2 2 3
输出 #3
4
注意
在第一个示例中,用 $$$3$$$ 颜色绘制元素的一种可能方法是:
- 用第一种颜色绘制元素:$$$a_1=10$$$ 和 $$$a_4=5$$$,
- 用第二种颜色绘制元素$$$a_3=3$$$,
- 用第三种颜色绘制元素:$$$a_2=2$$$、$$$a_5=4$$$ 和 $$$a_6=2$$$。
在第二个示例中,您可以使用一种颜色来绘制所有元素。
在第三个示例中,用 $$$4$$$ 颜色绘制元素的一种可能方法是:
- 用第一种颜色绘制元素:$$$a_4=4$$$、$$$a_6=2$$$ 和 $$$a_7=2$$$,
- 用第二种颜色绘制元素:$$$a_2=6$$$、$$$a_5=3$$$ 和 $$$a_8=3$$$,
- 用第三种颜色绘制元素$$$a_3=5$$$,
- 用第四种颜色绘制元素$$$a_1=7$$$。