You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given an Array A[] and the length of the array is N and also given an integer K. You need to rearrange this array such that,
for each i from ,\(1 <= i <= N-K+1\),
\(S_i= A_i + A_{i+1} + A_{i+2} + ... + A_{i+(K-1)}\)
and \(S_i\) is equal for all i.
for example, \(A [] \)= {1,2,1} and K=2.
\(S_1= A_1 + A_2 = 1 + 2 = 3\)
\(S_2= A_2 + A_3 = 2 + 1 = 3\)
Since, \(S_1 = S_2\), it's a beautiful array.
Before rearrange this array, you can do following operation:

• Choose indices i, \(1 <= i <= N\), and changes its value any positive integer d. (Ex. A [i] = d).

Input

First Line Contain T, the number of test cases.
In each test case, First line two positive integers N and K.
In each test case, Second line an array A [] and the length of the array is N.

\(1 <= T <= 10^5\)
\(1 <= N <= 3 * 10^5\)
\(1 <= K <= N\)
\(1 <= A[] <= 10^9\)

It's guranteed that sum of N overall test case doesn't exceed \(3 * 10^5\).

Output

In each test case, print minimum operation required to make array beautiful.

Sample

2
4 2
1 2 3 4
2 1
2 1

2
1

First Test case, Array A = {1,2,3,4}.
if we change index 3 with value 2, then array A = {1,2,2,4}.
if we change index 4 with value 1, then array A = {1,2,2,1}.
Now array A = {1,2,2,1}.
if we rearrange Array A = {2, 1, 2, 1}.
\(S_1 = 2 + 1 = 3\)
\(S_2 = 1 + 2 = 3\)
\(S_3 = 2 + 1 = 3\)
Since \(S_1 = S_2 = S_3 \), array is beautiful.
minimum operation required is 2.