E1. Square-Free Division (easy version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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?InputThe 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.OutputFor each test case print a single integer  — the answer to the problem.ExampleInput
35 018 6 2 4 15 06 8 1 24 81 01Output
3
2
1
NoteIn the first test case the division may be as follows:  [18, 6]  [2, 4]  [1] 
35 018 6 2 4 15 06 8 1 24 81 01
3 2 1 
['data structures', 'dp', 'greedy', 'math', 'number theory', 'two pointers', '*1700']