Множество свободное от k-делимости — это множество целых чисел, в котором не существует двух целых чисел, таких, что первое число равно другому, умноженному на k. То есть, во множестве не существует двух целых чисел x и y (x < y), таких, что y = x·k.
Вам дан набор, состоящий из n различных положительных целых чисел. Ваша задача — найти размер наибольшего его подмножества свободного от k-делимости.
Выходные данные
В единственной строке выходных данных выведите размер наибольшего подмножества свободного от k-делимости для {a1, a2, ..., an}.
Примечание
В первом тестовом примере одно из возможных наибольших подмножеств свободных от 2-делимости: {4, 5, 6}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
2 3 6 5 4 10
|
3
|