Counting Distinct Elements in Every K-Sized Window

Given an array ARR of size N and an integer K, determine the number of distinct elements in every K-sized window of the array. A 'K' sized window is defined as a continuous subarray of length K within the array.

Input

The first line contains an integer 'T', the number of test cases.
For each test case:
- The first line contains two integers, 'N' and 'K', where 'N' is the size of the array and 'K' is the window size.
- The second line contains 'N' space-separated integers representing the elements of the array 'ARR'.

Output

For each test case, output an array of integers where each integer represents the count of distinct elements in each consecutive 'K' sized window of 'ARR'. Each result should be on a new line.

Example

Input:

ARR = [1, 2, 1, 3, 4, 2, 3], K = 3

Output:

[2, 3, 3, 3, 3]

Explanation:

The distinct element count for each window of size 3 in the array is:

• Window-1: {1, 2, 1} → 2 distinct elements (1, 2)
• Window-2: {2, 1, 3} → 3 distinct elements (2, 1, 3)
• Window-3: {1, 3, 4} → 3 distinct elements (1, 3, 4)
• Window-4: {3, 4, 2} → 3 distinct elements (3, 4, 2)
• Window-5: {4, 2, 3} → 3 distinct elements (4, 2, 3)

Constraints

• 1 <= T <= 10
• 1 <= N <= 10⁵
• 1 <= K <= N
• 1 <= ARR[i] <= 10⁹
• Time limit: 1 second per test case

Note

You are not required to print anything explicitly. Implement the function to return the desired results as specified.