물건 포장하기

Albert는 Alice의 가게에서 포장하여 우편으로 부치는 일을 도와주기로 했다. 물건을 포장하는 일은 번거롭지만 간단하다.

우선 길이가 B로 동일한 상자를 여러 개 준비한다 (몇 개 준비해야 충분한지 계산하는 것이 Albert의 일이다). 하루 동안 총 R대의 트럭이 공장에서 가게로 물건을 배달해오는데, 한 번에 한 대의 트럭에서 물건을 모두 배달 받은 후 다음 트럭에서 물건을 배달 받는 식으로 진행한다. 각 트럭은 모두 똑같이 n개의 물건을 배달하며, 각 물건에 1번부터 n번까지 고유한 번호가 붙어 있어서 이 순서대로 물건을 꺼내야만 한다.
i번째 물건의 길이를 v[i]라 하자.

아래 그림은 R = 4, n = 3 이고 v = [2, 2, 3]인 경우를 보여준다. 즉 각각의 트럭에 길이가 2, 2, 3인 물건이 실려있고, 이 순서로 (좌에서 우로) 물건을 꺼낸다고 생각하면 된다.

Albert는 이 물건들을 길이가 B인 상자에 순서대로 넣어서 잘 포장하여 목적지에 부치는 일을 도와주기로 했다. 단, 앞서 언급한대로 1번 트럭부터 R번 트럭까지, 그리고 각 트럭에서 물건을 번호 순서대로 꺼내서 넣어야만 한다.

예를 들어 B = 5 인 경우, 위 예제의 경우 상자가 총 여섯 개 필요하다. 아래 그림은 좌측부터 순서대로 여섯 개의 상자를 이용하여 Albert가 물건을 채운 모습을 나타낸다.

• 먼저, 1번 트럭에서 1번과 2번 물건을 꺼내 첫 번째 상자에 담는다. 3번 물건을 넣기에는 상자의 길이가 모자라므로 두 번째 상자가 필요하다.
• 두 번째 상자에는 1번 트럭에서 꺼낸 3번 물건과 2번 트럭에서 꺼낸 1번 물건을 넣을 수 있다.
• 세 번째 상자에는 2번 트럭에서 꺼낸 2번과 3번 물건을 넣을 수 있다.
• 네 번째 상자에는 3번 트럭에서 1번과 2번 물건을 넣을 수 있다.
• 다섯 번째 상자에는 3번 트럭에서 꺼낸 3번 물건과 4번 트럭에서 꺼낸 1번 물건을 넣을 수 있다.
• 마지막 여섯 번째 상자에는 4번 트럭에서 2번과 3번 물건을 넣을 수 있다.
• 따라서 이 경우 총 여섯 개의 상자가 필요하다.

Albert는 트럭이 배달을 시작하기 전 미리 상자가 몇 개나 필요할지 계산해서 Alice에게 알려주어야 한다.

입력으로 n, B, R, 그리고 물건의 길이를 나타내는 v 값들이 주어졌을 때, 길이가 B인 상자가 총 몇 개 필요한지 계산해보자.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 두 줄에 걸쳐 주어진다.

테스트 케이스의 첫 줄에 n, B, R이 주어진다. 둘째 줄에 물건의 길이를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• 1 ≤ T ≤ 10
• 1 ≤ n, B ≤ 4,000
• (각 물건 i에 대하여) 1 ​​≤ v[i] ≤ B
• 1 ≤ R ≤ 1015