#878 lino Wants to Get Consent

Statement

Statement language

lino and Osaragi visit houses to obtain residents' consent for a school festival.

The houses are numbered from $1$ to $N$ in the order they must be visited. This order cannot be changed.

Obtaining consent at house $i$ takes $a_i$ minutes.

They can spend at most $K$ minutes visiting houses on a normal day. If they rest for an entire day, they can spend up to $2K$ minutes on the immediately following day. The extra time cannot be carried over to any later day.

The houses visited on a single day must form a contiguous segment of the required visiting order. Obtaining consent at one house cannot be split across multiple days.

Find the minimum number of days required to obtain consent from all houses in order. Rest days are included in the count.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum number of days required to obtain consent from all houses, on one line.

Constraints

$1 \le T \le 100\,000$ .
$1 \le N \le 100\,000$ .
$1 \leq K$ .

Subtasks

#	Score	Constraints
1	10	$K = 1$ in every test case.
2	30	$N \le 50$ in every test case.
3	60	No additional constraints.

Samples

Sample 1

Input

1
3 3
2 2 2

Output

2

By resting on the first day, they can spend $6$ minutes on the second day and visit all three houses.

Sample 2

Input

1
4 5
2 3 4 1

Output

2

They can visit houses $1$ and $2$ on the first day and houses $3$ and $4$ on the second day.