G. Странная красота
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп нашёл на улице массив $$$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$$$ стал красивым.

Входные данные

В первой строке содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — элементы массива $$$a$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное число элементов массива, которые необходимо удалить, чтобы массив $$$a$$$ стал красивым.

Пример
Входные данные
4
5
7 9 3 14 63
3
2 14 42
4
45 9 3 18
3
2 2 8
Выходные данные
2
0
1
0
Примечание

В первом наборе входных данных удаление элементов $$$7$$$ и $$$14$$$ сделает массив $$$a$$$ красивым.

Во втором наборе входных данных массив $$$a$$$ уже является красивым.

В третьем наборе входных данных удаление одного из элементов $$$45$$$ или $$$18$$$ сделает массив $$$a$$$ красивым.

В четвертом наборе входных данных массив $$$a$$$ уже является красивым.