CF1891E.Brukhovich and Exams

The boy Smilo is learning algorithms with a teacher named Brukhovich.

Over the course of the year, Brukhovich will administer $n$ exams. For each exam, its difficulty $a_i$ is known, which is a non-negative integer.

Smilo doesn't like when the greatest common divisor of the difficulties of two consecutive exams is equal to $1$. Therefore, he considers the sadness of the academic year to be the number of such pairs of exams. More formally, the sadness is the number of indices $i$ ($1 \leq i \leq n - 1$) such that $gcd(a_i, a_{i+1}) = 1$, where $gcd(x, y)$ is the greatest common divisor of integers $x$ and $y$.

Brukhovich wants to minimize the sadness of the year of Smilo. To do this, he can set the difficulty of any exam to $0$. However, Brukhovich doesn't want to make his students' lives too easy. Therefore, he will perform this action no more than $k$ times.

Help Smilo determine the minimum sadness that Brukhovich can achieve if he performs no more than $k$ operations.

As a reminder, the greatest common divisor (GCD) of two non-negative integers $x$ and $y$ is the maximum integer that is a divisor of both $x$ and $y$ and is denoted as $gcd(x, y)$. In particular, $gcd(x, 0) = gcd(0, x) = x$ for any non-negative integer $x$.

男孩斯米洛正在跟随一位名叫布鲁霍维奇的老师学习算法。

在这一年中，布鲁霍维奇将举行 $n$ 次考试。每次考试的难度 $a_i$ 是已知的，它是一个非负整数。

斯米洛不喜欢连续两次考试的难度的最大公约数等于 $1$ 的情况。因此，他将这一学年的“悲伤值”定义为满足该条件的连续考试对的数量。更准确地说，悲伤值等于满足 $gcd(a_i, a_{i+1}) = 1$ 的下标 $i$ 的个数（其中 $1 \leq i \leq n - 1$），这里 $gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

布鲁霍维奇希望最小化斯米洛这一学年的悲伤值。为此，他可以将任意一次考试的难度设置为 $0$。但布鲁霍维奇并不想让学生们过得太轻松，因此他最多只执行该操作 $k$ 次。

请帮助斯米洛计算：若布鲁霍维奇最多执行 $k$ 次操作，所能达到的最小悲伤值是多少？

需要提醒的是，两个非负整数 $x$ 和 $y$ 的最大公约数（GCD）是指能同时整除 $x$ 和 $y$ 的最大整数，记作 $gcd(x, y)$。特别地，对任一非负整数 $x$，均有 $gcd(x, 0) = gcd(0, x) = x$。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 10^5$) — the total number of exams and the maximum number of exams that can be simplified, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, a_3, \ldots, a_n$ — the elements of array $a$, which are the difficulties of the exams ($0 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, output the minimum possible sadness that can be achieved by performing no more than $k$ operations.

对于每个测试用例，输出通过执行不超过 $k$ 次操作所能达到的最小悲伤值。

In the first test case, a sadness of $1$ can be achieved. To this, you can simplify the second and fourth exams. After this, there will be only one pair of adjacent exams with a greatest common divisor (GCD) equal to one, which is the first and second exams.

In the second test case, a sadness of $0$ can be achieved by simplifying the second and fourth exams.

在第一个测试用例中，可以达到悲伤值 $1$。为此，你可以简化第二场和第四场考试。此后，仅剩一对相邻考试的最大公约数（GCD） 为 $1$，即第一场与第二场考试。

在第二个测试用例中，通过简化第二场和第四场考试，可以达到悲伤值 $0$。