Мальчик Смайло учится алгоритмам у учителя по имени Брухович.
В течение года Брухович проведет \(n\) контрольных. Для каждой контрольной известна ее сложность \(a_i\) — неотрицательное целое число. Смайло не нравится, когда у двух последовательных контрольных наибольший общий делитель их сложностей равен \(1\). Поэтому он считает грустностью учебного года количество таких пар контрольных. Формально, грустность — это количество таких индексов \(i\) (\(1 \leq i \leq n - 1\)), что \(gcd(a_i, a_{i+1}) = 1\), где \(gcd(x, y)\) — наибольший общий делитель чисел \(x\) и \(y\).
Брухович хочет минимизировать грустность учебного года для Смайло. Для этого он может сделать сложность любой контрольной равной \(0\). Понятно, что Брухович не хочет слишком сильно облегчать жизнь своим ученикам. Поэтому он выполнит описанное выше действие не более \(k\) раз.
Помогите Смайло узнать, какой минимальной грустности может добиться Брухович, если применит не более \(k\) операций.
Напоминаем, что наибольшим общим делителем (НОД) двух неотрицательных целых чисел \(x\) и \(y\) называется максимальное такое число, которое является делителем и \(x\), и \(y\), обозначается как \(gcd(x, y)\). В частности, \(gcd(x, 0) = gcd(0, x) = x\) для любого целого неотрицательного \(x\).
Выходные данные
Для каждого набора входных данных выведите минимальную возможную грустность, которую можно достичь, выполнив не более \(k\) операций.
Примечание
В первом наборе входных данных можно достичь грустности, равной \(1\). Для этого нужно упростить вторую и четвертую контрольные. После этого будет только одна пара соседних контрольных, имеющая НОД, равный единице - это первая и вторая контрольные.
Во втором наборе входных данных можно достичь грустности, равной \(0\), упростив вторую и четвертую контрольные.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
5 2
1 3 5 7 9
5 2
3 5 7 9 11
8 2
17 15 10 1 1 5 14 8
5 3
1 1 1 1 1
5 5
1 1 1 1 1
19 7
1 1 2 3 4 5 5 6 6 7 8 9 10 1 1 1 2 3 1
15 6
2 1 1 1 1 2 1 1 2 1 1 1 2 1 2
5 2
1 1 1 1 2
5 2
1 0 1 0 1
|
1
0
2
2
0
5
5
2
1
|