Steve có nhiệm vụ lập trình minh họa cho một trò chơi mới với cỗ bài ~n~ quân. Đây là trò chơi một người. Trên mỗi quân bài có ghi một số nguyên trong phạm vi từ ~1~ đến ~m~. Người chơi được chia ~k~ quân bài trên cùng của cỗ bài. Phần còn lại của cỗ bài được đặt trên bàn. Trong suốt qua trình chơi, không lúc nào người chơi không được cầm trên tay quá ~k~ quân bài. Ở mỗi thời điểm có thể thực hiện một trong ~3~ hành động sau:
- Bỏ một quân bài đang cầm trên tay xuống tập bài dập. Quân bài này sẽ không được dùng lại trong quá trình chơi tiếp theo,
- Nếu số bài cầm trên tay ít hơn ~k~, người chơi có thể lấy một quân bài trên cùng ở cổ bài trên bàn, bổ sung vào số bài mình đang cầm,
- Hạ quân bài có số ~x~ xuống bàn nếu trước đó đã hạ các quân bài với các số ~1, 2, . . ., x-1~ và quân bài số ~x~ chưa hạ.
Trò chơi kết thúc khi không thể thực hiện được hành động nào trong số kể trên. Mục tiêu của trò chơi là làm thế nào để hạ được nhiều quân bài nhất có thể.
Steve lập trình minh họa nên biết trước số ghi trên các quân bài ở cỗ bài trên bàn và biết các quân được chia cho người chơi. Hãy xác định số tối đa các quân bài có thể hạ xuống bàn.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên ~t~ – số lượng tests trong file ~(1 \leq t \leq 10^5)~,
- Dữ liệu mỗi test ghi trên ~2~ dòng:
- Dòng đầu tiên chứa ~3~ số nguyên ~n, m~ và ~k~ ~(1 \leq n, m \leq 10^5, 1 \leq k \leq n)~,
- Dòng thứ hai chứa n số nguyên ~a_1, a_2, . . ., a_n ~ ~(1 \leq a_i \leq m, i = 1 \div n)~.
Kết quả:
Kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên, xác định số quân bài tối đa có thể hạ.
Sample Input
3
4 3 1
3 2 1 2
1 2 1
2
5 5 2
4 2 1 4 3
Sample Output
2
0
4
Nguồn: Thầy Nguyễn Thanh Tùng
Comments