Tham dự Đại hội thể thao quốc tế, có ~n~ đoàn được mời tham gia. Các đoàn được đánh số hiệu từ 1 đến ~n~, biết ~s_i~ là số người trong đoàn thứ ~i~ (~i~ = 1,2, … , ~n~). Trong buổi giao lưu giữa các đoàn, Ban tổ chức lên kế hoạch tổ chức một trò chơi. Trò chơi cần nhiều nhóm tham gia, mỗi nhóm có đúng ~k~ người và không có nhóm nào có hai người cùng đoàn. Chú ý là có thể có người không được xếp vào bất cứ nhóm nào. Ban đầu, chỉ có ~R~ đoàn có số hiệu 1, 2, … , ~R~ tham gia. Trò chơi rất thú vị nên sau mỗi một lượt chơi, các đoàn có số hiệu ~R~ + 1, ~R~ + 2, … , ~n~ lần lượt đăng kí tham gia. Để trò chơi thêm phần hấp dẫn, mỗi khi có đoàn mới đăng kí tham gia Ban tổ chức muốn xếp lại các nhóm để có nhiều nhóm nhất mà mỗi nhóm có đúng ~k~ người và không có nhóm nào có hai người cùng đoàn.

Yêu cầu:

Cho ~s_1~, ~s_2~, … , ~s_n~ và ~R~, hãy giúp Ban tổ chức tính số nhóm nhiều nhất có thể xếp được sau mỗi lượt các nhóm đăng kí tham gia.

Input

Gồm ~T~ bộ dữ liệu, mỗi bộ theo khuôn dạng sau:

• Dòng thứ nhất gồm ba số nguyên ~n~, ~k~, ~R~ (~n~ ≤ ~10^5~; ~k~ ≤ 100);
• Dòng thứ hai chứa ~n~ số nguyên dương ~s_i~ (1 ≤ ~s_i~ ≤ ~10^9~ , i = 1, 2, … , ~n~);

Output

Gồm ~T~ dòng, mỗi dòng gồm ~n~ - ~R~ số nguyên, số thứ ~j~ là số nhóm tối đa xếp được khi đoàn ~R~ + ~j~ đăng kí tham gia.

Ví dụ:

Input

1
5 4 4
4 4 4 4 4

Output

5