시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Пете подарили на день рождения новую карточную игру <<Салют>>. Эта игра предназначена для одного человека. В комплект игры входит колода, состоящая из $n$ карт. На каждой карте написано целое число от 1 до $m$. 

Игра происходит следующим образом. Колода карт перемешивается, и игрок берет в руку верхние $k$ карт из колоды. В каждый момент времени игрок может держать в руке не более $k$ карт. Есть три различных вида хода.

  • \item{Сбросить любую карту, находящуюся в руке. Сброшенная карта отправляется в снос и не может быть далее использована в игре.}
  • \item{Если в колоде еще есть карты, то взять в руку верхнюю карту колоды.  Такой ход можно сделать только, если в руке у игрока строго меньше, чем $k$ карт.}
  • \item{Выложить карту из руки на стол. Карту с числом $x$ можно выложить  в том случае, если игрок до этого уже выложил на стол карты с числами $1, 2, \ldots, x-1$,  но еще не выложил карту с числом $x$.}

Игра заканчивается, когда нельзя сделать ни одного из вышеперечисленных ходов. Цель игры состоит в том, чтобы выложить на стол как можно больше карт. 

Петя подсмотрел, в каком порядке лежат карты в колоде, и теперь хочет сделать ходы так, чтобы максимизировать число выложенных карт. Помогите ему выяснить, какое максимальное число карт ему удастся выложить.

입력

Входной файл содержит несколько тестовых примеров. В первой строке находится целое число $T$ --- количество тестовых примеров ($1 \le T \le 10^5$). Следующие $2T$ строк содержат описание тестовых примеров. 

Описание каждого тестового примера состоит из двух строк. В первой строке находятся целые числа $n$, $m$ и $k$ --- количество карт в колоде, максимальное число, которое может быть написано на карте, и максимальное количество карт в руке ($1 \le n, m \le 10^5$, $1 \le k \le n$).

Во второй строке находятся $n$ целых чисел $a_i$ --- числа, написанные на картах, в том порядке, в котором они лежат в колоде, начиная с самой верхней карты ($1 \le a_i \le m$).

Сумма $n$ во всех тестовых примерах не превосходит $10^5$.

출력

Для каждого тестового примера в отдельной строке выведите единственное целое число --- максимальное число карт, которое можно выложить.

예제 입력 1

3
4 3 1
3 2 1 2
1 2 1
2
5 5 2
4 2 1 4 3

예제 출력 1

2
0
4

힌트

В третьем примере следует играть следующим образом. Исходно у Пети в руках 4 и 2. Петя сбрасывает 4, берет из колоды 1. Теперь у него в руках 2 и 1. Петя выкладывает 1, затем 2. Теперь у него в руке нет карт. Он берет из колоды 4, затем берет из колоды 3. Теперь у него в руке 4 и 3, он выкладывает 3 и затем выкладывает 4.