长度为 $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$。