Вам дана последовательность целых чисел \(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\) цвета (следует покрасить каждый элемент в отдельный цвет).
Выходные данные
Выведите минимальное количество цветов, которое нужно, чтобы покрасить все элементы корректным образом.
Примечание
В первом примере можно покрасить элементы в \(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\).