놀이공원 (Small)

이 놀이공원에서 가장 인기가 많은 놀이기구는 롤러코스터다. 혼자 온 손님도 있고 여러 명이 한 그룹으로 온 손님도 있는데, 그룹으로 온 손님은 그룹 전원이 함께 타야만 탑승한다. 한 번 타 본 손님은 또 타고 싶어 해서 내리자마자 다시 줄을 선다. 요금은 한 번 탈 때마다 한 사람당 1유로다. 오늘 이 롤러코스터가 올릴 매출을 예측하라.

롤러코스터에는 한 번에 최대 $k$명이 탄다. 그룹은 줄을 서서 기다리고 맨 앞 그룹부터 차례로 탑승한다. 모든 그룹이 다 탔거나 다음 차례 그룹 전원이 앉을 자리가 남지 않으면, 빈자리가 있어도 그대로 출발한다. 뒤 그룹이 앞 그룹을 앞질러 타는 일은 없다. 내린 그룹은 탑승한 순서 그대로 줄 맨 뒤에 다시 선다. 롤러코스터는 하루에 $R$번 출발한다.

예를 들어 $R = 4$, $k = 6$이고 1명, 4명, 2명, 1명인 네 그룹이 이 순서로 서 있다고 하자. 첫 번째 출발에는 1명 그룹과 4명 그룹이 타고 한 자리를 비운 채 떠난다. 다음 2명 그룹이 앉을 자리가 모자라고, 맨 뒤 1명 그룹은 앞 그룹을 앞지를 수 없기 때문이다. 두 그룹이 줄 뒤로 돌아가면 줄은 2명, 1명, 1명, 4명이 된다. 두 번째 출발에는 2명, 1명, 1명이 타서 모두 4명이고, 줄은 4명, 2명, 1명, 1명이 된다. 세 번째 출발에는 4명과 2명이 타서 모두 6명이고, 줄은 1명, 1명, 4명, 2명이 된다. 마지막 출발에는 1명, 1명, 4명이 타서 모두 6명이다. 그래서 이날 매출은 21유로다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지고, 각 테스트 케이스는 두 줄이다. 첫 줄에는 공백으로 구분한 정수 $R$, $k$, $N$이 주어진다. 둘째 줄에는 공백으로 구분한 정수 $g_0, g_1, \dots, g_{N-1}$이 주어진다. $g_i$는 줄에서 $i+1$번째 그룹의 인원수다.

제약

• $1 \le T \le 50$
• $1 \le R \le 1000$
• $1 \le k \le 100$
• $1 \le N \le 10$
• $1 \le g_i \le 10$
• $g_i \le k$

각 테스트 케이스마다 한 줄에 Case #X: Y 형식으로 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 그날 롤러코스터가 올린 매출이다.