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?

N/A

N/A

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