E. Брухович и контрольные
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Смайло учится алгоритмам у учителя по имени Брухович.

В течение года Брухович проведет $$$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$$$.

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

В первой строке содержится единственное число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

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

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

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

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

Пример
Входные данные
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
Примечание

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

Во втором наборе входных данных можно достичь грустности, равной $$$0$$$, упростив вторую и четвертую контрольные.