Five Nights at Freddy's 1 Song — The Living Tombstone

Let $$$n, m, \ell$$$ be positive integers. You have made the unfortunate decision to work as a night guard at Freddy Fazbear's Pizzeria, where there are $$$m$$$ animatronics numbered $$$1, \ldots, m$$$ waiting to jumpscare you.

The night consists of $$$\ell$$$ seconds, numbered $$$1, \ldots, \ell$$$. The $$$j$$$-th of the $$$m$$$ animatronics has a danger level $$$d_j$$$, and initially $$$d_1 = \ldots = d_m = 0$$$. Every second, the danger level of exactly one animatronic will increase by $$$1$$$, and throughout the night, you are able to observe all values of $$$d_j$$$ at the current time. For example, if $$$m = 2$$$, one possible list of danger levels after $$$5$$$ seconds is $$$[d_1, d_2] = [2, 3]$$$.

You are not defenseless, however. At each of the $$$n$$$ fixed times $$$a_i$$$ ($$$1 \leq a_1 \lt \ldots \lt a_n \leq \ell$$$), you can shine your flashlight on exactly one animatronic $$$j_i$$$ of your choice. This occurs immediately after the $$$a_i$$$-th second and sets its danger level back to zero, i.e. $$$d_{j_i} := 0$$$. Note that this choice is made independently for each flashlight use $$$a_i$$$. Continuing the example from before, if $$$a_1 = 5$$$ and you choose to flash the second animatronic at that time, the danger levels after $$$5$$$ seconds will be $$$[d_1, d_2] = [2, 0]$$$.

Let the overall danger be the maximum danger across all animatronics, i.e. $$$\max_{1 \leq j \leq m} d_j$$$. You will lose if the overall danger at the end of the night (after $$$\ell$$$ seconds) is greater than $$$x$$$. Find the minimum value of $$$x$$$ such that regardless of the actions of the animatronics, you can guarantee that overall danger will be less than or equal $$$x$$$.

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 three integers $$$n$$$, $$$m$$$, and $$$\ell$$$ ($$$1 \leq n, m, \ell \leq 2 \cdot 10^5, n \leq \ell, 1 \leq m \cdot \ell \leq 2 \cdot 10^5$$$) — the number of flashlight actions, animatronics, and the length of the night, respectively.

The next line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_1 \lt \ldots \lt a_n \leq \ell$$$) — the times at which you get to shine your flashlight.

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

Output

For each test case, output a single integer — the minimum $$$x$$$ such that you can guarantee that your final danger level is at most $$$x$$$.

Note

In the first test case, there are $$$2$$$ animatronics and a night length of $$$10$$$, and you get to flash after the $$$10$$$-th second. We will show that $$$x = 5$$$ is always possible. After $$$10$$$ seconds, notice that one animatronic must have at least $$$5$$$ danger, and the other must have at most $$$5$$$ danger. So, we can flash the higher one and get a final danger level at most $$$5$$$. It can be shown that $$$5$$$ is the minimum possible value of $$$x$$$.

In the second test case, there is only one animatronic and a night length of $$$32$$$. Notice that in this case, the animatronic just increments its danger by $$$1$$$ each second. So, after the $$$25$$$-th second, we reset its danger to $$$0$$$. Seven more seconds pass before the night ends, so the final danger we get is always $$$7$$$.

In the third test case, it can be proven that the minimum possible value of $$$x$$$ is $$$19$$$.

One Night At Freddy's

Examples