CF1497E2 Square-free division (hard version)

这是该问题的困难版本。唯一的区别在于本版本中 $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$。

对于每个测试用例，输出一个整数，表示该问题的答案。

在第一个测试用例中，可以将数组更改为 $[\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]$ 由 ChatGPT 4.1 翻译