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

Это простая версия задачи. Единственное отличие  — в этой версии задачи $$$k = 0$$$.

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

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

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

Пример
Входные данные
3
5 0
18 6 2 4 1
5 0
6 8 1 24 8
1 0
1
Выходные данные
3
2
1
Примечание

В первом наборе входных можно сделать такое разбиение:

  • $$$[18, 6]$$$
  • $$$[2, 4]$$$
  • $$$[1]$$$