기립 박수

오페라의 개막 공연 날이며, 친구는 프리마돈나(여성 주역 가수)이다. 당신은 관객석에 있지 않지만, 모든 관객이 일어서서 그녀를 위해 손뼉을 치는 기립 박수를 그녀가 반드시 받게 하고 싶다.

처음에는 모든 관객이 앉아 있다. 모든 관객에게는 수줍음 정도가 있다. 수줍음 정도가 $S_{i}$인 관객은 적어도 $S_{i}$명의 다른 관객이 이미 일어나 손뼉을 칠 때까지 기다리며, 그 조건이 충족되면 즉시 일어나 손뼉을 친다. $S_{i}$ = 0이면, 그 관객은 다른 사람이 무엇을 하든 항상 즉시 일어나 손뼉을 친다. 예를 들어, $S_{i}$ = 2인 관객은 처음에는 앉아 있지만, 나중에 적어도 다른 두 사람이 일어서서 손뼉을 치는 것을 본 뒤 일어나 손뼉을 친다.

당신은 모든 관객의 수줍음 정도를 알고 있으며, 결국 관객 모두가 일어나 손뼉을 치도록 보장하기 위해 프리마돈나의 친구들을 관객으로 추가 초대할 준비가 되어 있다. 이 친구들은 각각 당신이 원하는 어떤 수줍음 값이라도 가질 수 있으며, 반드시 서로 같을 필요는 없다. 기립 박수를 보장하기 위해 초대해야 하는 친구의 최소 수는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 240초. 0 ≤ $S_{max}$ ≤ 6.

큰 데이터 세트

시간 제한: 480초. 0 ≤ $S_{max}$ ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 관객 중 가장 수줍음이 많은 사람의 최대 수줍음 정도인 $S_{max}$가 먼저 주어지고, 그 뒤에 $S_{max}$ + 1개의 한 자리 숫자로 이루어진 문자열이 주어진다. 이 문자열의 k번째 숫자(0부터 세기 시작)는 수줍음 정도가 k인 관객의 수를 나타낸다. 예를 들어, 문자열 "409"는 $S_{i}$ = 0인 관객이 네 명이고 $S_{i}$ = 2인 관객이 아홉 명이며, $S_{i}$ = 1이거나 그 밖의 값을 가진 관객은 없다는 뜻이다. 처음에는 각 수줍음 정도를 가진 사람이 항상 0명 이상 9명 이하임에 유의한다.

문자열은 절대로 0으로 끝나지 않는다. 이는 관객석에 항상 적어도 한 명이 있다는 뜻임에 유의한다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 초대해야 하는 친구의 최소 수이다.

케이스 #1에서는 아무도 추가할 필요 없이 관객이 결국 스스로 기립 박수를 보낸다. 먼저 $S_{i}$ = 0인 관객이 일어서고, 그다음 $S_{i}$ = 1인 관객이 일어서는 식이다.

케이스 #2에서는 $S_{i}$ = 0인 친구를 초대해야 하지만, 그것만으로도 모든 관객을 일어서게 하기에 충분하다.

케이스 #3에서 한 가지 최적해는 $S_{i}$ = 2인 관객 두 명을 추가하는 것이다.

케이스 #4에서는 관객이 단 한 명뿐이며, 그는 즉시 일어선다. 친구를 초대할 필요가 없다.