Busy Beaver はこの問題のために面白いストーリーを書くのが面倒だったので、形式的な問題文だけを提供します。

$M$-数列を、$1$ 以上 $M$ 以下の正の整数からなる数列と定義します。

$M$-数列が $K$-good であるとは、隣接する任意の2要素の絶対差が $K$ 以下であることを指します。例えば、$[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$) が含まれます。

各テストケースの最初の行には、4つの整数 $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$) が含まれます。

テストケースの2行目には $a_1, \dots, a_N$ ($1 \le a_i \le M$) が含まれます。$N = 0$ の場合、この行はスキップされます。

$a$ のすべての $K$-good な部分列の長さが $L$ 以下であることが保証されています。 さらに、すべてのテストケースにおける $N$ の総和は $4 \cdot 10^5$ を超えません。

出力

各テストケースについて、$b$ の要素数の最大値を1行で出力してください。問題の制約下において、最大値は常に存在し、$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$ 以下です。

2番目のサンプルテストケースでは、$M$-数列 $b$ の一例として $[1, 1, 5, 4, 2, 5]$ が挙げられます。この数列の $2$-good な部分列（例えば $[5, 4, 2]$ や $[1, 1, 2]$ など）はすべて長さが $L = 3$ 以下です。

3番目のサンプルテストケースでは、可能な $b$ は $b = a$ のみであることが示せます。