A. Гелифиш и пылающий пион
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гелифиш ненавидит математические задачи, но ей нужно закончить домашнее задание по математике:

Гелифишу дан массив из $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$.

Ей нужно выполнять следующую двухшаговую операцию, пока все элементы массива $$$a$$$ не станут равными:

  1. Выбрать два индекса $$$i$$$, $$$j$$$, удовлетворяющие $$$1 \leq i, j \leq n$$$ и $$$i \neq j$$$.
  2. Заменить $$$a_i$$$ на $$$\gcd(a_i, a_j)$$$.

Теперь Гелифиш спрашивает вас о минимальном количестве операций, необходимых для достижения её цели.

Можно доказать, что Гелифиш всегда может достичь своей цели.

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

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

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

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для достижения её цели.

Пример
Входные данные
3
3
12 20 30
6
1 9 1 9 8 1
3
6 14 15
Выходные данные
4
3
3
Примечание

В первом наборе входных данных следующий способ минимизирует количество операций:

  1. Выбрать $$$i = 3$$$ и $$$j=2$$$ и заменить $$$a_3$$$ на $$$\gcd(a_3,a_2) = \gcd(30, 20) = 10$$$, тогда $$$a$$$ становится $$$[12, 20, 10]$$$.
  2. Выбрать $$$i=1$$$ и $$$j=3$$$ и заменить $$$a_1$$$ на $$$\gcd(a_1,a_3) = \gcd(12, 10) = 2$$$, тогда $$$a$$$ становится $$$[2, 20, 10]$$$.
  3. Выбрать $$$i=2$$$ и $$$j=1$$$ и заменить $$$a_2$$$ на $$$\gcd(a_2,a_1) = \gcd(20, 2) = 2$$$, тогда $$$a$$$ становится $$$[2, 2, 10]$$$.
  4. Выбрать $$$i=3$$$ и $$$j=1$$$ и заменить $$$a_3$$$ на $$$\gcd(a_3,a_1) = \gcd(10, 2) = 2$$$, тогда $$$a$$$ становится $$$[2, 2, 2]$$$.