C. Equalizing 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Blanca has a sequence of $$$n$$$ integers $$$a_1, \ldots, a_n$$$ and a positive integer $$$k$$$. She can perform operations of the following two types:

  1. Choose an index $$$i$$$ and add $$$1$$$ to $$$a_i$$$.
  2. Choose $$$k+1$$$ distinct indices $$$i_1, \ldots, i_k, i_{k+1}$$$, add $$$k$$$ to $$$a_{i_{k+1}}$$$, and subtract $$$1$$$ from each of $$$a_{i_1}, \ldots, a_{i_k}$$$.

Blanca wants to make all $$$n$$$ numbers equal by applying these operations zero or more times. Help her determine the minimum number of times she needs to perform operations of the first type. (She can perform as many operations of the second type as she wants).

Input

The first line contains an integer $$$T$$$, the number of test cases to process.

Each case consists of a line with two integers $$$n$$$ and $$$k$$$, followed by a line with the $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

Output

For each case, print a line with the minimum number of operations of the first type needed to equalize the numbers.

Scoring
  1. (12 points) $$$k = 1$$$.
  2. (22 points) $$$k = 2$$$.
  3. (14 points) $$$n \geq k+2$$$.
  4. (25 points) The sum of $$$n^2$$$ for all cases is at most $$$10^6$$$.
  5. (27 points) No additional restrictions.
Example
Input
4
5 3
2 1 2 4 3
3 1
1 2 3
3 2
1 2 3
5 1
1000000000 1000000000 1000000000 999999999 1000000000
Output
3
0
3
1
Note
  • $$$1 \leq T \leq 10^4$$$.
  • $$$2 \leq n \leq 10^6$$$. The sum of $$$n$$$ for all cases is at most $$$10^6$$$.
  • $$$1 \leq k \leq n-1$$$.
  • $$$1 \leq a_i \leq 10^9$$$ for all $$$1 \leq i \leq n$$$.