E2. Бесквадратное разбиение (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие  — в этой версии задачи $$$0 \leq k \leq 20$$$.

Дан массив $$$a_1, a_2, \ldots, a_n$$$ из $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно число  — ответ на задачу.

Пример
Входные данные
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
Примечание

В первом наборе входных данных можно сначала изменить массив следующим образом: $$$[\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]$$$