CF1497E1 Square-free division (easy version)

This is the easy version of the problem. The only difference is that in this version $ k = 0 $ . There is an array $ a_1, a_2, \ldots, a_n $ of $ n $ positive integers. You should divide it into a minimal number of continuous segments, such that in each segment there are no two numbers (on different positions), whose product is a perfect square. Moreover, it is allowed to do at most $ k $ such operations before the division: choose a number in the array and change its value to any positive integer. But in this version $ k = 0 $ , so it is not important. What is the minimum number of continuous segments you should use if you will make changes optimally?

The first line contains a single integer $ t $ $ (1 \le t \le 1000) $ — the number of test cases. The first line of each test case contains two integers $ n $ , $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ k = 0 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^7 $ ). It's guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case print a single integer — the answer to the problem.

In the first test case the division may be as follows: - $ [18, 6] $ - $ [2, 4] $ - $ [1] $