기립 박수 (Large)

오늘 밤은 오페라 개막 공연이고, 친구가 프리마 돈나(주연 여성 성악가)를 맡았다. 나는 객석에 없지만, 친구가 기립 박수를 받게 하고 싶다. 기립 박수는 관객 전원이 일어서서 박수를 치는 것을 뜻한다.

처음에는 관객이 모두 앉아 있다. 관객마다 수줍음 수치가 있다. 수줍음 수치가 $S_i$인 관객은 이미 일어나서 박수를 치는 다른 관객이 $S_i$명 이상이 될 때까지 기다리고, 그 조건이 채워지는 순간 곧바로 일어나서 박수를 친다. $S_i = 0$인 관객은 다른 사람과 상관없이 언제나 곧바로 일어나서 박수를 친다. 예를 들어 $S_i = 2$인 관객은 처음에는 앉아 있다가, 다른 두 사람이 일어나서 박수를 치는 것을 본 뒤에 일어선다.

관객 전원의 수줍음 수치를 알고 있고, 프리마 돈나의 친구를 객석에 더 초대해서 결국 모두가 일어서게 만들 수 있다. 초대하는 친구에게는 원하는 수줍음 수치를 하나씩 정해 줄 수 있고, 서로 같을 필요는 없다. 기립 박수를 보장하려면 친구를 최소 몇 명 초대해야 하는지 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄이고, 관객 중 가장 수줍은 사람의 수줍음 수치 $S_{max}$와 길이가 $S_{max} + 1$인 숫자 문자열이 공백으로 구분되어 주어진다. 이 문자열의 $k$번째 숫자(0부터 센다)는 수줍음 수치가 $k$인 관객의 수를 나타낸다. 예를 들어 문자열 "409"는 $S_i = 0$인 관객이 4명, $S_i = 2$인 관객이 9명이고 다른 수치의 관객은 없다는 뜻이다. 각 수줍음 수치의 인원은 항상 0명 이상 9명 이하다.

문자열은 0으로 끝나지 않는다. 따라서 관객은 항상 한 명 이상이다.

제한

• $1 \le T \le 100$
• $0 \le S_{max} \le 1000$

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 초대해야 하는 친구의 최소 인원이다.

첫 번째 예제의 케이스 1에서는 아무도 초대하지 않아도 관객끼리 기립 박수를 만든다. 먼저 $S_i = 0$인 관객이 일어서고, 그다음 $S_i = 1$인 관객이 일어서는 식이다.

케이스 2에서는 $S_i = 0$인 친구를 한 명 초대해야 하고, 그것으로 객석 전체가 일어선다.

케이스 3에서는 $S_i = 2$인 관객을 두 명 추가하는 것이 최적의 답 중 하나다.

케이스 4에서는 관객이 한 명뿐이고 그 사람은 곧바로 일어선다. 초대할 친구는 없다.