Reference: Codeforces 1497E1 — Square-Free Division, Easy Version

You are given an array of ~n~ positive integers:

~a_1, a_2, \ldots, a_n~

Divide the array into the minimum possible number of non-empty contiguous segments such that no segment contains two elements at different positions whose product is a perfect square.

The input also contains an integer ~k~. In this easy version, ~k~ is always equal to ~0~, so no array elements may be changed.

Input

• The first line contains one integer ~t~, the number of test cases.
• For each test case, the first line contains ~n~ and ~k~, where ~k = 0~.
• The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.

Output

• For each test case, print one integer: the minimum number of contiguous segments.

Constraints

• ~1 \le t \le 1000~
• ~1 \le n \le 2 \times 10^5~
• ~k = 0~
• ~1 \le a_i \le 10^7~
• The sum of ~n~ over all test cases does not exceed ~2 \times 10^5~.

Example 1

Input:

3
5 0
18 6 2 4 1
5 0
6 8 1 24 8
1 0
1

Output:

3
2
1