Đăng ký kênh truyền hình

Đài truyền hình BerTV mỗi ngày phát đúng một tập của một trong $k$ chương trình. Bạn biết trước lịch phát sóng của $n$ ngày sắp tới: dãy số nguyên $a_1,a_2,\dots ,a_n$, trong đó $a_i$ là chương trình được phát vào ngày thứ $i$.

Gói đăng ký được bán theo từng chương trình: mua một chương trình nghĩa là xem được mọi tập của chương trình đó, và mỗi chương trình phải mua riêng.

Bạn muốn xem truyền hình liên tục $d$ ngày. Hãy tìm số chương trình ít nhất cần đăng ký sao cho tồn tại một đoạn $d$ ngày liên tiếp mà mọi tập phát trong đoạn đó đều thuộc các chương trình đã mua. Được phép xem nhiều hơn $d$ ngày liên tiếp, miễn là có ít nhất một đoạn $d$ ngày thoả mãn.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa ba số nguyên $n$, $k$, $d$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số chương trình ít nhất cần đăng ký.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le 2·{10}^5$
• $1\le k\le {10}^6$
• $1\le d\le n$
• $1\le a_i\le k$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ