J. Jaywalking
time limit per test
1 second
memory limit per test
32 megabytes
input
standard input
output
standard output

Parallel sidewalks $$$A$$$ and $$$B$$$ of length $$$n$$$ units are separated by a road. There are also $$$m$$$ crosswalks with traffic lights connecting the two sidewalks. All $$$m$$$ lights are in sync, and they are all green as SnowballSH arrives at location $$$1$$$ unit of sidewalk $$$A$$$ at time $$$t=0$$$. However, the light colors alternate every $$$k$$$ seconds. For example, the lights are green on seconds $$$t=0,1,\dots,k-1$$$, red on seconds $$$t=k,k+1,\dots,2k-1$$$, and then green again on seconds $$$t=2k,2k+1,\dots,3k-1$$$, etc.

SnowballSH needs to get to location $$$n$$$ unit of sidewalk $$$B$$$ by crossing the road at one of the crosswalks. At each second, SnowballSH may perform one of the following actions:

  • Walk forward $$$1$$$ unit on the current crosswalk.
  • If there is a crosswalk at SnowballSH's location and the light is green, cross the road to the other sidewalk, without moving forward.
  • Do nothing and wait at his current location.

After his action, the time advances by one second.

Please help SnowballSH determine the fastest possible time he can arrive at location $$$n$$$ on sidewalk $$$B$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

The first line of each test case contains three integers $$$n, m, k$$$ ($$$1 \le m \le n \le 10^5$$$; $$$1 \le k \le 10^9$$$) — the length of the sidewalks, the number of crosswalks, and the number of seconds before the light colors alternate, respectively.

The second line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$, indicating there is a crosswalk at location $$$c_i$$$ unit for each $$$i=1,2,\dots,m$$$.

Output

For each test case, print one integer — the minimum number of seconds SnowballSH needs to arrive at location $$$n$$$ on sidewalk $$$B$$$.

Example
Input
3
6 2 1
2 5
12 3 5
9 6 8
1234 1 123
666
Output
6
14
1307
Note

For the first test case, there are two possible crosswalks SnowballSH can take:

  • Take the crosswalk at location $$$2$$$ units. Then, he needs to walk for $$$2-1=1$$$ second, wait $$$1$$$ second for the light to change to green, spend $$$1$$$ second crossing, and then spend $$$6-2=4$$$ more seconds walking. Therefore, he needs a total of $$$7$$$ seconds.
  • Take the crosswalk at location $$$5$$$ units. Then, he needs to walk for $$$5-1=4$$$ seconds, spend $$$1$$$ second crossing, and then spend $$$6-5=1$$$ more second walking. Therefore, he needs a total of $$$6$$$ seconds.

Overall, SnowballSH should take the second crosswalk. It can be shown that it is not possible for SnowballSH to take less than $$$6$$$ seconds.

For the third test case, there is only one crosswalk SnowballSH can take. The light turns red at $$$t=123\times 5=615$$$ seconds and turns green again at $$$t=123\times 6=738$$$ seconds. Since SnowballSH arrives at the crosswalk at $$$t=666-1=665$$$, he needs to wait $$$738-665=73$$$ seconds. The time SnowballSH needs is therefore $$$(666-1)+73+1+(1234-666)=1307$$$ seconds.