Busy Beaver 太懶了，不想為這道題寫一個有趣的故事，所以他直接給你一個正式的敘述。

定義一個 $M$-序列 為一個由正整數組成的序列，其中每個元素都在 $1$ 到 $M$ 之間（包含 $1$ 與 $M$）。

若一個 $M$-序列中，任意相鄰兩元素的絕對差值至多為 $K$，則稱該序列為 $K$-good。例如，$[1, 2, 3, 5, 5, 3, 2, 1]$ 是 $2$-good 且 $2024$-good，但不是 $1$-good。我們同時將長度為 $0$ 或 $1$ 的 $M$-序列視為 $K$-good。

給定正整數 $N, M, K, L$ 以及一個長度為 $N$ 的 $M$-序列 $a_1, \dots, a_N$，請找出一個 $M$-序列 $b$ 的最大可能長度，使得：

• $b$ 以 $a$ 作為前綴；且
• $b$ 的每一個 $K$-good 子序列長度至多為 $L$。

回顧一下，序列的子序列是透過刪除原序列中的某些元素（可能全部刪除或一個都不刪除），且不改變剩餘元素順序所得到的序列。

輸入格式

輸入包含多組測試資料。第一行包含一個正整數 $T$ ($1 \le T \le 2 \cdot 10^5$)，代表測試資料的組數。

每組測試資料的第一行包含四個整數 $N, M, K, L$ ($0 \le N \le 2 \cdot 10^5$, $1 \le M \le 10^9$, $0 \le K \le 10^9$, $1 \le L \le 10^9$)。

每組測試資料的第二行包含 $a_1, \dots, a_N$ ($1 \le a_i \le M$)。若 $N = 0$，則此行會被跳過。

保證 $a$ 的每一個 $K$-good 子序列長度至多為 $L$。 此外，所有測試資料的 $N$ 總和不超過 $4 \cdot 10^5$。

輸出格式

對於每組測試資料，輸出一行，代表 $b$ 的最大長度。可以證明在題目限制下，最大值一定存在且不超過 $9 \cdot 10^{18}$。

子任務

• ($5$ 分) $M \le K + 1$。
• ($5$ 分) $K = 0$。
• ($10$ 分) $N = 0$。
• ($15$ 分) $N = 1$。
• ($30$ 分) 所有測試資料的 $N, M, K, L$ 總和皆不超過 $3000$。
• ($35$ 分) 無額外限制。

範例

輸入 1

3
3 3 1 3
1 3 2
0 5 2 3
7 7 2 3
1 4 2 7 7 1 6

輸出 1

5
6
7

說明

在第一個範例測試資料中，一個可能的 $M$-序列 $b$ 為 $[1, 3, 2, 3, 1]$，其 $1$-good 子序列（例如 $[3, 2, 3]$ 和 $[3, 2, 1]$）長度皆至多為 $L = 3$。

在第二個範例測試資料中，一個可能的 $M$-序列 $b$ 為 $[1, 1, 5, 4, 2, 5]$，其 $2$-good 子序列（例如 $[5, 4, 2]$ 和 $[1, 1, 2]$）長度皆至多為 $L = 3$。

在第三個範例測試資料中，可以證明唯一的可能 $b$ 即為 $b = a$。