B. Ритмичная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём двоичную строку $$$s$$$ длины $$$m$$$ периодичной, если существует целое число $$$k$$$ ($$$1 \le k \lt m$$$), для которого $$$s_i = s_{i+k}$$$ для каждого $$$i$$$ от $$$1$$$ до $$$m-k$$$ включительно. Символы строки нумеруются с $$$1$$$. Минимальное такое $$$k$$$ называется периодом строки.

Назовём строку $$$s$$$ ритмичной, если она периодична и среди первых $$$p$$$ символов строки (где $$$p$$$ — период строки) ровно один символ 1.

Например, строка 0010010 периодична с периодом $$$p=3$$$ и ритмична: среди первых трёх символов ровно один символ 1. Строка 0110110 тоже периодична с периодом $$$p=3$$$, но не ритмична: среди первых трёх символов два символа 1.

Дан массив $$$a$$$ из $$$n$$$ целых чисел и строка $$$s$$$, изначально состоящая из $$$10^{18}$$$ нулей. Для каждого элемента $$$a_i$$$ все символы строки, номера которых делятся на $$$a_i$$$, заменяются на единицы. Иными словами, единицами становятся символы на позициях $$$a_i,2a_i,3a_i,\ldots$$$, не превосходящих длину строки. Повторная замена символа на единицу ничего не меняет.

Например, если $$$a=[3,7,5,3]$$$, то строка $$$s$$$ будет начинаться с 001011101101011...

Перед выполнением этих изменений вы можете удалить любые элементы массива $$$a$$$. Найдите минимальное количество элементов, которые нужно удалить, чтобы получившаяся строка $$$s$$$ была ритмичной.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длину массива $$$a$$$.

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

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Выходные данные

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

Пример
Входные данные
4
4
3 7 5 3
3
4 8 12
4
6 10 20 30
3
2 3 5
Выходные данные
2
0
1
2
Примечание

В первом наборе входных данных можно удалить элементы $$$7$$$ и $$$5$$$. Тогда строка будет начинаться с 001001001... и будет ритмичной с периодом $$$3$$$.

Во втором наборе входных данных ничего удалять не нужно. Строка будет начинаться с 000100010001... и будет ритмичной с периодом $$$4$$$.

В третьем наборе входных данных достаточно удалить элемент $$$6$$$. Полученная строка будет ритмичной с периодом $$$10$$$.

В четвёртом наборе входных данных нужно оставить любой один элемент массива.