← 返回题目列表

Codeforces · 1891/E

E. 布鲁霍维奇和考试

中文机器翻译题面 查看原题

男孩 Smilo 正在跟随一位名叫 Brukhovich 的老师学习算法。

在这一年中,Brukhovich 将管理 $$$n$$$ 考试。对于每个考试,其难度 $$$a_i$$$ 是已知的,它是一个非负整数。

Smilo 不喜欢连续两次考试难度的最大公约数等于 $$$1$$$。因此,他认为一学年的悲伤就是这样的成对考试的次数。更正式地说,悲伤度是索引的数量 $$$i$$$ ($$$1 \leq i \leq n - 1$$$) 使得 $$$gcd(a_i, a_{i+1}) = 1$$$,其中 $$$gcd(x, y)$$$ 是整数 $$$x$$$ 和 $$$y$$$ 的最大公约数。

布鲁霍维奇希望尽量减少斯米洛这一年的悲伤。为此,他可以将任何考试的难度设置为 $$$0$$$。然而,布鲁霍维奇不想让他的学生的生活变得太轻松。因此,他执行此操作的次数不会超过 $$$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$$$ — 数组 $$$a$$$ 的元素,它们是考试的难度 ($$$0 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出通过执行不超过 $$$k$$$ 操作可以实现的最小可能悲伤。

示例

输入 #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

1
0
2
2
0
5
5
2
1

注意

在第一个测试用例中,可以实现 $$$1$$$ 的悲伤。为此,您可以简化第二次和第四次考试。此后,将只有一对最大公约数(GCD)等于 1 的相邻考试,即第一次和第二次考试。

在第二个测试用例中,可以通过简化第二个和第四个考试来实现 $$$0$$$ 的悲伤。