长度为 $n$ 的街道被积雪覆盖，将街道划分为 $n$ 段，第 $i$ 段的积雪量为 $a_i$，保证 $0 \le a_i \le m$ 且 $a_i$ 为整数。
天依与言和要来清理积雪，每次清理有 2 种选择：
- 天依从位置 1 走到位置 $x$，将积雪清理掉 $c$，再走回位置 1。同时，因为在雪地上移动，位置 $1 \sim x$ 的积雪量减少 1，即 $\forall i \in [1, x-1], a_i := a_i - 1, a_x := a_x - c - 1$。
- 言和从位置 $n$ 走到位置 $x$，将积雪清理掉 $c$，再走回位置 $n$。同时，因为在雪地上移动，位置 $x \sim n$ 的积雪量减少 1，即 $\forall i \in [x+1, n], a_i := a_i - 1, a_x := a_x - c - 1$。
任意时刻，积雪量对 $0$ 取 $\max$。
天依与言和想知道，最少进行多少次清理后（即最小化两人清理次数总和），能将所有积雪清除，即 $\forall i \in [1, n], a_i = 0$。
输入格式
本题有多组测试数据。
首先输入一行两个数 $T, tid$，$T$ 表示数据组数，$tid$ 表示子任务编号（样例的子任务编号为 0）。
对于每组数据：
第一行三个整数 $n, m, c$。
第二行 $n$ 个整数 $a_1 \sim a_n$。
输出格式
对于每组数据，输出一行一个整数表示答案。
测试样例
样例输入 1
1 0 5 5 1 1 3 2 3 1
样例输出 1
2
样例解释 1
天依走到位置 4 清理，积雪量变为 $[0, 2, 1, 1, 1]$。
言和走到位置 2 清理，积雪量变为 $[0, 0, 0, 0, 0]$。
共 2 次清理。
样例 2
见附加文件中的 snow.in 与 snow.ans。这个样例中有 100 组 $n = 10, m = 10$ 的数据。
数据范围
对于 $100\%$ 的数据，$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$。
| 子任务编号 | $n$ | $m$ | 特殊限制 | 分值 | 子任务依赖 |
|---|---|---|---|---|---|
| 1 | $\le 5 \times 10^5$ | $\leq 5 \times 10^5$ | $c = 0$ | 2 | $ $ |
| 2 | $\leq 2$ | 无 | 3 | ||
| 3 | $\leq 5$ | $ \leq 5$ | $T \le 10^5$ | 4 | |
| 4 | $\leq 50$ | $\leq 50$ | $\sum n, \sum m \le 200$ | 10 | 3 |
| 5 | $\leq 300$ | $ \leq 300$ | $\sum n, \sum m \le 600$ | 10 | 4 |
| 6 | $\leq 2\,000$ | $\leq 2\,000$ | $\sum n, \sum m \le 4000$ | 10 | 5 |
| 7 | $\leq 5 \times 10^4$ | $\leq 5 \times 10^4$ | $c \le 20, \sum n, \sum m \le 10^5$ | 20 | $ $ |
| 8 | $\sum n, \sum m \le 10^5$ | 15 | 6, 7 | ||
| 9 | $\leq 5 \times 10^5$ | $\leq 5 \times 10^5$ | $c \le 20$ | 10 | 1, 7 |
| 10 | 无 | 15 | 2, 8, 9 |