19979번 - Игра 다국어

문제

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

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

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

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

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

입력

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

Описание каждого тестового примера состоит из двух строк. В первой строке находятся целые числа $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$.

출력

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

제한

힌트

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