无平方因子划分（困难版）

• 时间限制：2 秒
• 内存限制：256 MiB

题目背景

本题为困难版，区别在于允许修改的次数满足 $0\le k\le 20$。

题目描述

给定一个包含 $n$ 个正整数的数组 $a_1,a_2,\ldots,a_n$。你需要把它划分成尽可能少的连续非空段，使每一段内都不存在两个不同位置的数，其乘积为完全平方数。

在划分之前，你可以进行至多 $k$ 次修改。每次修改可以选择一个数组元素，并把它改为任意正整数。

请输出最优修改后所需的最少段数。

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例第一行包含两个整数 $n,k$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示最少段数。

样例输入

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
2
1

数据范围

对所有数据，$1\le t\le 1000$，$1\le n\le 2\times10^5$，$0\le k\le20$，$1\le a_i\le10^7$，且单个输入文件中所有测试用例的 $n$ 之和不超过 $2\times10^5$。