Đại tướng Thiên Quang chuẩn bị đối đầu với một cuộc tập kích quy mô lớn từ quân địch. Để thiết lập tuyến phòng thủ, Thiên Quang duyệt một đạo quân gồm ~n~ đơn vị đang xếp thành một hàng dọc, với chỉ số sức mạnh lần lượt là ~a_1, a_2, \ldots, a_n~.

Thiên Quang vô cùng tin tưởng và giao cho phó tướng Bá Lộc nhiệm vụ điều phối đạo quân này vào đúng ~k~ cứ điểm phòng ngự chiến lược. Do yêu cầu khắt khe về đội hình hành quân, Bá Lộc cần phải chia các đơn vị vào ~k~ cứ điểm thỏa mãn các điều kiện sau:

• mỗi cứ điểm phải có ít nhất một đơn vị;

• mỗi đơn vị phải thuộc về một cứ điểm;

• nếu đơn vị thứ ~i~ và đơn vị thứ ~j~ (~i < j~) thuộc cùng một cứ điểm, tất cả các đơn vị ~i, i + 1, i + 2, \ldots, j~ phải thuộc cùng một cứ điểm.

Sức mạnh phòng thủ của một cứ điểm là tổng chỉ số sức mạnh của các đơn vị thuộc cứ điểm đó.

Tin tình báo cho biết rằng mỗi đạo quân địch có sức mạnh là ~s~. Một cứ điểm được coi là mong manh nếu sức mạnh phòng thủ của cứ điểm này nhỏ hơn hoặc bằng ~s~.

Là một phó tướng tài, Bá Lộc muốn xem xét hết mọi trường hợp có thể xảy ra, kể cả trường hợp tệ nhất. Trong tất cả các cách điều phối đạo quân hợp lệ, hãy giúp Bá Lộc tìm xem số lượng cứ điểm mong manh nhiều nhất có thể điều phối được.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \le t \le 10^4~) — số lượng test case. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa ba số nguyên ~n~, ~k~ và ~s~ (~1 \le k \le n~, ~1 \le s \le 10^9~) — số lượng đơn vị quân, số lượng cứ điểm cần phân bổ và sức mạnh tấn công của quân địch vào mỗi cứ điểm.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — chỉ số sức mạnh của các đơn vị quân, theo thứ tự xếp hàng.

Output

Với mỗi test case, in ra một số nguyên — số lượng cứ điểm mong manh nhiều nhất có thể điều phối.

Scoring

Sample Input 1

3
5 3 10
1 2 3 4 5
7 3 10
3 12 5 7 15 2 8
4 2 5
1 2 3 4

Sample Output 1

3
2
1

Notes

Ở test case đầu tiên, Bá Lộc có thể điều phối đội hình thành ~k = 3~ cứ điểm ~[1, 2, 3], [4], [5]~. Sức mạnh phòng thủ các cứ điểm lần lượt là ~6~, ~4~ và ~5~, đều không quá ~s = 10~, nên có ~3~ cứ điểm mong manh.

Ở test case thứ hai, Bá Lộc có thể điều phối thành ~k = 3~ cứ điểm như sau: ~[3], [12, 5, 7, 15], [2, 8]~. Sức mạnh phòng thủ của các cứ điểm lần lượt là ~3~, ~39~ và ~10~. Đáp án là ~2~ do cứ điểm đầu tiên và cuối cùng có sức mạnh phòng thủ không quá ~s = 10~. Có thể chỉ ra rằng không có cách chia nào để cả ~3~ cứ điểm đều mong manh.

Ở test case thứ ba, một cách điều phối để có ~1~ cứ điểm mong manh là ~[1, 2], [3, 4]~. Không có cách điều phối nào để cả hai cứ điểm đều mong manh.