Поликарп нашёл на улице массив \(a\) из \(n\) элементов.
Поликарп изобрёл свой критерий красоты массива. Он называет массив \(a\) красивым, если для каждой пары различных индексов \(i \ne j\) должно быть выполнено хотя бы одно из следующих условий:
- \(a_i\) делится на \(a_j\);
- \(a_j\) делится на \(a_i\).
Например, если:
- \(n=5\) и \(a=[7, 9, 3, 14, 63]\), то массив \(a\) не является красивым (при \(i=4\) и \(j=2\) не выполняется ни одно из условий выше);
- \(n=3\) и \(a=[2, 14, 42]\), то массив \(a\) является красивым;
- \(n=4\) и \(a=[45, 9, 3, 18]\), то массив \(a\) не является красивым (при \(i=1\) и \(j=4\) не выполняется ни одно из условий выше);
Некрасивые массивы расстраивают Поликарпа, поэтому он хочет удалить некоторые элементы из массива \(a\) так, чтобы он стал красивым. Помогите Поликарпу определить, какое наименьшее число элементов массива необходимо удалить, чтобы массив \(a\) стал красивым.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное число элементов массива, которые необходимо удалить, чтобы массив \(a\) стал красивым.
Примечание
В первом наборе входных данных удаление элементов \(7\) и \(14\) сделает массив \(a\) красивым.
Во втором наборе входных данных массив \(a\) уже является красивым.
В третьем наборе входных данных удаление одного из элементов \(45\) или \(18\) сделает массив \(a\) красивым.
В четвертом наборе входных данных массив \(a\) уже является красивым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
7 9 3 14 63
3
2 14 42
4
45 9 3 18
3
2 2 8
|
2
0
1
0
|