Trang sức

Vân có \(N\) đồ trang sức trên kệ được đánh số \(1, 2, \ldots, N\) từ trái sang phải. Đồ trang sức có nhiều loại khác nhau, được biểu thị bằng số nguyên dương. Món đồ thứ \(i\) trên kệ là loại \(A_i\).

Hôm nay Vân sẽ bay ra nước ngoài gặp gia đình và muốn mang theo càng nhiều đồ trang sức càng tốt. Tuy nhiên, vì đang vội nên Vân phải lấy một khoảng đồ trang sức liên tiếp trên kệ. Nghĩa là Vân sẽ chọn hai chỉ số, \(l\) và \(r\), và lấy tất cả các món đồ trang sức được đánh số \(l, l + 1, \ldots, r - 1, r\). Ngoài ra, do các quy tắc về thuế, an ninh sân bay sẽ vứt bỏ tất cả các loại đồ trang sức mà Vân có nhiều hơn \(S\) món trong đồ mang theo.

Ví dụ: giả sử \(S = 2\), Vân mang theo sáu món đồ trang sức: một loại \(0\), hai loại \(1\) và ba loại \(2\). Vân sẽ mất tất cả các nữ trang loại \(2\) ở sân bay!

Yêu cầu: Hãy giúp Vân chọn \(l\) và \(r\) sao cho cô ấy có thể mang được nhiều đồ trang sức nhất cho gia đình mình.

Input

• Dòng đầu tiên ghi duy nhất một số nguyên \(T \leq 5\) là số lượng trường hợp test. Mỗi nhóm dòng trong số \(T\) nhóm dòng sau bao gồm:
• Dòng một chứa hai số nguyên dương \(N\) và \(S\) (\(S \leq N \leq 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i\) là \(A_i\) (\(A_i \leq 10^5\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên là số đồ trang sức tối đa mà Vân có thể mang ra nước ngoài thăm gia đình.

Example

1
6 2
1 1 4 1 4 4

4

Scoring

\begin itemize

• Subtask \(1\) (15 điểm): \(N \le 300\).
• Subtask \(2\) (15 điểm): \(N \le 1000\).
• Subtask \(3\) (70 điểm): Không có ràng buộc nào khác.
  \end itemize