A. Bestie
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Друзья попросили вас сделать наибольший общий делитель (НОД) всех элементов массива равным $$$1$$$. За одну операцию вы можете сделать следующее:

  • Выбрать произвольный индекс в массиве $$$1 \leq i \leq n$$$;
  • Сделать $$$a_i = \gcd(a_i, i)$$$, где $$$\gcd(x, y)$$$ обозначает НОД чисел $$$x$$$ и $$$y$$$. Стоимость такой операции равна $$$n - i + 1$$$.

Вам нужно найти минимальную суммарную стоимость операций, которые нужно сделать, чтобы НОД всех элементов массива стал равен $$$1$$$.

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

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

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

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

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

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

Можно показать, что это всегда можно сделать.

Пример
Входные данные
9
1
1
1
2
2
2 4
3
3 6 9
4
5 10 15 20
5
120 60 80 40 80
6
150 90 180 120 60 30
6
2 4 6 9 12 18
6
30 60 90 120 125 125
Выходные данные
0
1
2
2
1
3
3
0
1
Примечание

В первом наборе входных данных НОД всего массива уже равен $$$1$$$, поэтому операции применять не нужно.

Во втором наборе входных данных можно выбрать $$$i = 1$$$. После этой операции $$$a_1 = \gcd(2, 1) = 1$$$. Стоимость этой операции равна $$$1$$$.

В третьем наборе входных данных можно выбрать $$$i = 1$$$, после этого массив $$$a$$$ будет равен $$$[1, 4]$$$. НОД этого массива равен $$$1$$$, а суммарная стоимость равна $$$2$$$.

В четвертом наборе входных данных можно выбрать $$$i = 2$$$, после этого массив $$$a$$$ будет равен $$$[3, 2, 9]$$$. НОД этого массива равен $$$1$$$, а суммарная стоимость равна $$$2$$$.

В шестом наборе входных данных можно выбрать $$$i = 4$$$ и $$$i = 5$$$, после этого массив $$$a$$$ будет равен $$$[120, 60, 80, 4, 5]$$$. НОД этого массива равен $$$1$$$, а суммарная стоимость равна $$$3$$$.