PIXL - This Time

⠀

You are managing a fleet of $$$n$$$ drones, each with an energy level $$$a_1, \ldots, a_n$$$. You are also given a positive integer $$$k$$$, which represents the maximum number of drones allowed to share the same energy level.

To prevent overloads, the drones automatically perform energy balancing operations as follows. While there exists an energy level that appears strictly more than $$$k$$$ times, they execute the following steps:

first, every drone $$$i$$$ whose energy $$$a_i$$$ appears earlier (that is, there exists $$$j \lt i$$$ with $$$a_j = a_i$$$) is marked;
then, for each marked drone, its energy is increased by $$$1$$$ unit;
then, the marks are removed.

The process stops once no energy level appears more than $$$k$$$ times. Determine how many energy balancing operations will be performed.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — the number of drones and the maximum allowed number of drones with the same energy level.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2n$$$) — the initial energy levels of the drones.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single line containing an integer: the number of energy balancing operations performed.

Note

In the first test case, the drones' energy levels evolve as follows:

at the beginning, $$$[1, 1, 1, 1, 1, 1]$$$;
after $$$1$$$ operation, $$$[1, 2, 2, 2, 2, 2]$$$;
after $$$2$$$ operations, $$$[1, 2, 3, 3, 3, 3]$$$;
after $$$3$$$ operations, $$$[1, 2, 3, 4, 4, 4]$$$.

After $$$3$$$ operations, every energy level appears at most $$$3$$$ times, so the process stops.

In the second test case, the energy levels change as follows: $$$[1, 3, 2, 1, 4] \rightarrow [1, 3, 2, 2, 4] \rightarrow [1, 3, 2, 3, 4] \rightarrow [1, 3, 2, 4, 4] \rightarrow [1, 3, 2, 4, 5]$$$. The process stops after $$$4$$$ operations.

Adjusting Drones

Examples