CF1891E Brukhovich and Exams

男孩 Smilo 正在和名叫 Brukhovich 的老师一起学习算法。 在这一年中，Brukhovich 将会安排 $n$ 场考试。每场考试的难度 $a_i$ 已知，且为非负整数。 Smilo 不喜欢相邻两场考试的难度的最大公约数等于 $1$。因此，他认为一学年的“悲伤值”是所有满足条件的考试对的数量。更正式地说，悲伤值是满足 $gcd(a_i, a_{i+1}) = 1$ 的下标 $i$ 的数量（$1 \leq i \leq n-1$），其中 $gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。 Brukhovich 想要尽量减少 Smilo 这一年的悲伤值。为此，他可以将任意场考试的难度设为 $0$。但 Brukhovich 又不想让学生们的生活太轻松，因此他最多只能进行 $k$ 次这样的操作。 请帮助 Smilo 计算，如果 Brukhovich 最多进行 $k$ 次操作，能达到的最小悲伤值是多少。 提醒：两个非负整数 $x$ 和 $y$ 的最大公约数（GCD）是同时整除 $x$ 和 $y$ 的最大整数，记作 $gcd(x, y)$。特别地，对于任意非负整数 $x$，有 $gcd(x, 0) = gcd(0, 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$，表示每场考试的难度（$0 \leq a_i \leq 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示在最多进行 $k$ 次操作后能达到的最小悲伤值。

在第一个测试用例中，最小悲伤值为 $1$。为此，你可以简化第二场和第四场考试。此后，只有第一场和第二场考试之间的相邻对的最大公约数为 $1$。 在第二个测试用例中，通过简化第二场和第四场考试，可以使悲伤值达到 $0$。 由 ChatGPT 4.1 翻译