Канал BerTV каждый день показывает один эпизод одного из $k$ сериалов. Вам известно расписание на ближайшие $n$ дней: последовательность целых чисел $a_1, a_2, \dots, a_n$, где $a_i$ — номер сериала, эпизод которого будет показан в $i$-й день.

Подписка на сериалы покупается целиком полностью на весь сериал, на каждый сериал подписка покупается отдельно.

Сколько минимум подписок надо купить, чтобы была возможность $d\ (1 \le d \le n)$ дней подряд смотреть эпизоды купленных по подписке сериалов? Иными словами, вы хотите купить минимальное количество сериалов, чтобы существовал некоторый отрезок из $d$ подряд идущих дней, в котором все эпизоды из сериалов по приобретённым подпискам.

Входные данные

В первой строке записано целое число $t$ ($1 \le t \le 10000$) — количество наборов входных данных в тесте. Далее следуют описания $t$ наборов входных данных.

Первая строка каждого из наборов содержит три целых числа $n, k$ и $d$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^6, 1 \le d \le n$). Вторая строка содержит $n$ целых чисел $a_1,a_2,…,a_n$ ($1 \le a_i \le k$), где $a_i$ — это номер сериала, который показывается в $i$-й день.

Гарантируется, что сумма значений $n$ по всем наборам входных данных в тесте не превосходит $2 \cdot 10^5$.

Выходные данные

Выведите $t$ целых чисел — ответы на заданные наборы входных данных в порядке их следования в тесте. Ответом на набор входных данных является минимальное количество сериалов, подписку на которые надо приобрести, чтобы была возможность $d$ дней подряд смотреть по BerTV эпизодов приобретённого сериала.

Подзадачи