这是问题的简单版本。唯一的区别是在此版本中 $$$k = 0$$$。
存在一个由 $$$n$$$ 正整数组成的数组 $$$a_1, a_2, \ldots, a_n$$$。您应该将其分成最少数量的连续段,使得每个段中不存在两个数字(位于不同位置)的乘积是完全平方数。
而且,在除法之前最多允许进行$$$k$$$这样的操作:在数组中选择一个数字,并将其值更改为任意正整数。但在这个版本中$$$k = 0$$$,所以这并不重要。
如果要进行最佳更改,应使用的最小连续段数是多少?
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 1000)$$$ — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$k = 0$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^7$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入 #1
3 5 0 18 6 2 4 1 5 0 6 8 1 24 8 1 0 1
输出 #1
3 2 1
注意
在第一个测试用例中,划分可能如下:
- $$$[18, 6]$$$
- $$$[2, 4]$$$
- $$$[1]$$$