Steve cần lập trình minh hoạ cho một trò chơi một người với một cỗ bài gồm ~n~ quân. Trên mỗi quân bài ghi một số nguyên trong đoạn từ ~1~ đến ~m~. Thứ tự các quân bài trong cỗ bài là cố định và đã biết trước.

Ban đầu, người chơi được chia đúng ~k~ quân bài trên cùng của cỗ bài để cầm trên tay. Các quân còn lại được đặt thành một chồng bài úp trên bàn. Trong suốt trò chơi, người chơi không bao giờ được cầm quá ~k~ quân.

Tại mỗi thời điểm, người chơi có thể thực hiện một trong ba hành động sau:

• Bỏ bài: chọn một quân bài đang cầm trên tay và bỏ xuống tập bài đã loại. Quân này sẽ không được dùng lại.
• Rút bài: nếu đang cầm ít hơn ~k~ quân, người chơi có thể rút quân trên cùng của chồng bài trên bàn và cầm lên tay.
• Hạ bài: hạ xuống bàn một quân bài có số ~x~ nếu trước đó người chơi đã hạ đủ các quân có số ~1,2,\dots,x-1~ và quân số ~x~ chưa được hạ.

Trò chơi kết thúc khi không thể thực hiện được bất kỳ hành động nào trong ba hành động trên. Mục tiêu là hạ được nhiều quân bài nhất có thể.

Yêu cầu

Với mỗi test, hãy xác định số lượng tối đa quân bài có thể hạ xuống bàn.

Dữ liệu

• Dòng đầu chứa số nguyên ~t~ — số lượng test ~(1 \le t \le 10^5)~.

• Mỗi test gồm 2 dòng:

  • Dòng 1 chứa ba số nguyên ~n, m, k~ ~(1 \le n, m \le 10^5,\ 1 \le k \le n)~.
  • Dòng 2 chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le m)~, là thứ tự các quân bài trong cỗ bài từ trên xuống dưới.
• Tổng всех ~n~ qua tất cả test không vượt quá ~10^5~.

Kết quả

Với mỗi test, in ra trên một dòng một số nguyên — số quân bài tối đa có thể hạ.

Ví dụ

Ví dụ 1

Input

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

Output

2
0
4

Giải thích

Ví dụ 1

• Test 1: Có thể hạ được ~1~ rồi ~2~, tổng ~2~ quân.
• Test 2: Chỉ có quân ~2~, không thể hạ ~1~ nên kết quả là ~0~.
• Test 3: Có thể hạ lần lượt ~1,2,3,4~, tổng ~4~ quân.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le t \le 10^5~, ~1 \le n,m \le 10^5~, ~1 \le k \le n~, ~1 \le a_i \le m~, và ~\sum n \le 10^5~.