← 返回题目列表

Codeforces · 1497/E2

E2. 无平方除法(硬版)

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

这是问题的困难版本。唯一的区别是在这个版本中 $$$0 \leq k \leq 20$$$。

存在一个由 $$$n$$$ 正整数组成的数组 $$$a_1, a_2, \ldots, a_n$$$。您应该将其分成最少数量的连续段,使得每个段中不存在两个数字(位于不同位置)的乘积是完全平方数。

而且,在除法之前最多允许进行$$$k$$$这样的操作:在数组中选择一个数字,并将其值更改为任意正整数。

如果要进行最佳更改,应使用的最小连续段数是多少?

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 1000)$$$ — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$、$$$0 \leq k \leq 20$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^7$$$)。

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

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

3
5 2
18 6 2 4 1
11 4
6 2 2 8 9 1 3 6 3 9 7
1 0
1

输出 #1

1
2
1

注意

在第一个测试用例中,可以通过以下方式更改数组:$$$[\underline{3}, 6, 2, 4, \underline{5}]$$$ (更改的元素带有下划线)。之后数组不需要划分,所以答案是$$$1$$$。

在第二个测试用例中,可以通过以下方式更改数组:$$$[6, 2, \underline{3}, 8, 9, \underline{5}, 3, 6, \underline{10}, \underline{11}, 7]$$$。之后这样的划分是最佳的:

- $$$[6, 2, 3]$$$
- $$$[8, 9, 5, 3, 6, 10, 11, 7]$$$