Вам дан массив \(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\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальную суммарную стоимость операций, которые нужно сделать, чтобы НОД всех элементов массива стал равен \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|