Busy Beaver는 이 문제에 대한 흥미로운 이야기를 쓸 만큼 부지런하지 못해서, 그냥 형식적인 문제 설명만 제공합니다.

$M$-수열을 $1$ 이상 $M$ 이하의 양의 정수들로 이루어진 수열로 정의합니다.

$M$-수열이 인접한 두 원소의 절댓값 차이가 최대 $K$일 때, 이를 $K$-좋은 수열이라고 합니다. 예를 들어, $[1, 2, 3, 5, 5, 3, 2, 1]$은 $2$-좋은 수열이자 $2024$-좋은 수열이지만, $1$-좋은 수열은 아닙니다. 길이가 $0$ 또는 $1$인 $M$-수열도 $K$-좋은 수열로 간주합니다.

양의 정수 $N, M, K, L$과 길이 $N$인 $M$-수열 $a_1, \dots, a_N$이 주어질 때, 다음 조건을 만족하는 $M$-수열 $b$의 최대 길이를 구하십시오.

• $b$는 $a$를 접두사로 가집니다.
• $b$의 모든 $K$-좋은 부분 수열의 길이는 최대 $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$-좋은 부분 수열의 길이는 최대 $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$-좋은 부분 수열들(예: $[3, 2, 3]$ 및 $[3, 2, 1]$)은 모두 길이가 최대 $L = 3$입니다.

두 번째 예제 테스트 케이스에서, 가능한 $M$-수열 $b$ 중 하나는 $[1, 1, 5, 4, 2, 5]$이며, 이 수열의 $2$-좋은 부분 수열들(예: $[5, 4, 2]$ 및 $[1, 1, 2]$)은 모두 길이가 최대 $L = 3$입니다.

세 번째 예제 테스트 케이스에서는 가능한 $b$가 $b = a$뿐임이 증명될 수 있습니다.