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 đố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 sau khi leo núi về khá mệt nên Tus không thể tính được mà đành phải nhờ các bạn giúp Tus tiếp nhé!

• Dòng đầu tiên gồm 1 số nguyên dương T là số lượng bộ test (1 \leq T \leq 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 \leq n \leq 100000, 0 \leq k \leq n), dòng thứ hai gồm n số nguyên là các phần tử mảng a (0 \leq a_i \leq 100000).

In ra 1 số nguyên duy nhất là độ dài chuỗi ngày ăn ngon tối đa có thể đạt được.

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