lino는 동의를 얻고 싶어

lino와 Osaragi는 학교 축제에 대한 주민 동의를 얻기 위해 집들을 방문한다.

방문해야 하는 집은 $1$번부터 $N$번까지 순서대로 나열되어 있으며, 방문 순서를 바꿀 수 없다.

$i$번 집에서 동의를 얻는 데 걸리는 시간은 $a_i$분이다.

하루에 사용할 수 있는 시간은 최대 $K$분이다. 단, 하루를 온전히 쉬면 바로 다음 날에는 최대 $2K$분을 사용할 수 있다. 쉬어서 늘어난 시간은 그다음 날까지 이월되지 않는다.

하루 동안 방문하는 집들은 방문 순서에서 연속된 구간이어야 한다. 한 집에서 동의를 얻는 일을 여러 날에 나누어 처리할 수 없다.

$1$번부터 $N$번까지 모든 집의 동의를 순서대로 얻는 데 필요한 최소 일수를 구하여라. 쉬는 날도 일수에 포함한다.

입력은 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 모든 집의 동의를 얻기 위해 필요한 최소 일수를 한 줄에 출력한다.

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