General Thiên Quang is preparing to face a large-scale ambush from the enemy army. To establish a defensive line, Thiên Quang reviews an army of ~n~ units arranged in a single line, with strength values ~a_1, a_2, \ldots, a_n~.

Thiên Quang trusts his deputy general Bá Lộc with the task of deploying this army to exactly ~k~ strategic defense positions. Due to strict marching formation requirements, Bá Lộc must divide the units into ~k~ positions satisfying the following conditions:

• each position must contain at least one unit;

• every unit must belong to exactly one position;

• if unit ~i~ and unit ~j~ (~i < j~) belong to the same position, then all units ~i, i + 1, i + 2, \ldots, j~ must also belong to that same position.

The defensive strength of a position is the sum of the strength values of the units in that position.

Intelligence reports say that each enemy attack has strength ~s~. A position is considered fragile if its defensive strength is less than or equal to ~s~.

As a skilled deputy general, Bá Lộc wants to consider all possible cases, including the worst one. Among all valid ways to deploy the army, help Bá Lộc find the maximum possible number of fragile positions.

Input

Each test contains multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10^4~) — the number of test cases. The description of each test case is as follows:

• The first line contains three integers ~n~, ~k~, and ~s~ (~1 \le k \le n~, ~1 \le s \le 10^9~) — the number of army units, the number of positions to divide them into, and the enemy attack strength against each position.

• The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — the strength values of the army units in order.

Output

For each test case, print one integer — the maximum possible number of fragile positions that can be formed

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

In the first test case, Bá Lộc can arrange the formation into ~k = 3~ positions ~[1, 2, 3], [4], [5]~. The defensive strengths of these positions are ~6~, ~4~, and ~5~, all of which are not greater than ~s = 10~, so there are ~3~ fragile positions.

In the second test case, Bá Lộc can arrange the formation into ~k = 3~ positions as follows: ~[3], [12, 5, 7, 15], [2, 8]~. The defensive strengths of these positions are ~3~, ~39~, and ~10~. The answer is ~2~ because the first and last positions have defensive strengths not greater than ~s = 10~. It can be shown that there is no way to split the army so that all ~3~ positions are fragile.

In the third test case, one way to arrange the formation to have ~1~ fragile position is ~[1, 2], [3, 4]~. There is no way to arrange it so that both positions are fragile.