A street of length $n$ is covered in snow, divided into $n$ segments. The amount of snow in the $i$-th segment is $a_i$, where $0 \le a_i \le m$ and $a_i$ is an integer.

Tianyi and Yanhe want to clear the snow. Each time they perform a cleaning operation, they have two choices:

• Tianyi walks from position 1 to position $x$, clears $c$ amount of snow at $x$, and walks back to position 1. Because of the movement on the snow, the snow amount in positions $1 \sim x$ decreases by 1. Specifically, $\forall i \in [1, x-1], a_i := a_i - 1$, and $a_x := a_x - c - 1$.
• Yanhe walks from position $n$ to position $x$, clears $c$ amount of snow at $x$, and walks back to position $n$. Because of the movement on the snow, the snow amount in positions $x \sim n$ decreases by 1. Specifically, $\forall i \in [x+1, n], a_i := a_i - 1$, and $a_x := a_x - c - 1$.

At any time, the amount of snow is $\max(0, \text{current amount})$.

Tianyi and Yanhe want to know the minimum number of cleaning operations required (i.e., minimizing the total number of operations performed by both) to clear all the snow, such that $\forall i \in [1, n], a_i = 0$.

Input

The input contains multiple test cases.

The first line contains two integers $T$ and $tid$, where $T$ is the number of test cases and $tid$ is the subtask ID (the subtask ID for the sample is 0).

For each test case:

The first line contains three integers $n, m, c$.

The second line contains $n$ integers $a_1 \sim a_n$.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

1 0
5 5 1
1 3 2 3 1

Output 1

2

Note

Tianyi walks to position 4 to clean, and the snow amounts become $[0, 2, 1, 1, 1]$.

Yanhe walks to position 2 to clean, and the snow amounts become $[0, 0, 0, 0, 0]$.

A total of 2 cleaning operations.

Example 2

See snow.in and snow.ans in the additional files. This example contains 100 test cases with $n = 10, m = 10$.

Constraints

For $100\%$ of the data, $1 \le T \le 10^5$, $1 \le n, m \le 5 \times 10^5$, $\sum n, \sum m \le 10^6$, $0 \le a_i \le m$, $0 \le c \le 5 \times 10^5$.