Vào một ngày đẹp trời tại Moskva, Tus đã gặp WN. Để thể hiện mình là một người biết quan tâm người khác, Tus đã tìm hiểu về chất lượng bữa ăn của WN trong ~n~ ngày tới. Vào ngày thứ ~i~ thì chất lượng bữa ăn là ~a_i~. Ngoài ra, Tus còn biết được sức khỏe của WN sẽ rất tốt nếu cô ấy được ăn một chuỗi ngày liên tiếp mà chất lượng bữa ăn mỗi ngày là như nhau (vì chất lượng bữa ăn thay đổi liên tục sẽ khiến cơ thể WN không kịp thích nghi), một chuỗi ngày như vậy được gọi là chuỗi ngày ăn ngon. Cho nên Tus đã nghĩ ra một cách cải thiện bữa ăn cho WN. Tus sẽ chọn ra một ngày bất kì và tự mình chuẩn bị bữa ăn cho WN để chất lượng bữa ăn ngày hôm đó đổi thành giá trị mà Tus mong muốn. Nhưng vì Tus khá bận nên anh chỉ có thể thay đổi được tối đa là ~k~ ngày bất kì. Vì vậy anh ấy tự hỏi rằng sau khi anh thay đổi chất lượng bữa ăn cho tối đa ~k~ ngày thì độ dài chuỗi ngày ăn ngon của WN tối đa là bao nhiêu. Do vừa leo núi về khá mệt nên Tus không thể tính được, đành phải nhờ các bạn giúp nhé!

Dữ liệu

• Dòng đầu tiên gồm 1 số nguyên dương ~T~ là số lượng bộ test ~(1 \le T \le 10)~.

• Mỗi test gồm 2 dòng: dòng thứ nhất chứa 2 số nguyên ~n, k~ là số ngày mà Tus tìm hiểu và số ngày tối đa mà Tus có thể thay đổi ~(1 \le n \le 10^5,\ 0 \le k \le n)~; dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^5)~.

Kết quả

Với mỗi test, in ra trên một dòng một số nguyên là độ dài chuỗi ngày ăn ngon tối đa có thể đạt được.

Ví dụ

Sample Input

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

Sample Output

4
2

Subtask

• ~40\%~ số test ~n \le 100~.

• ~60\%~ số test còn lại không có điều kiện thêm.