기립 박수 (스몰)

오페라 개막 공연 날이고, 당신의 친구가 프리마돈나(주연 여성 가수)를 맡았다. 당신은 객석에 앉지 못하지만 친구가 기립 박수를 받게 만들고 싶다. 기립 박수는 관객 전원이 자리에서 일어나 박수를 치는 것이다.

처음에는 관객 전원이 앉아 있다. 관객마다 부끄러움 수치가 정해져 있다. 부끄러움 수치가 $S_i$인 관객은 이미 일어나서 박수를 치는 관객이 $S_i$명 이상이 될 때까지 기다리고, 그 수를 채우면 곧바로 일어나서 박수를 친다. $S_i = 0$인 관객은 다른 사람이 무엇을 하든 언제나 즉시 일어나서 박수를 친다. 예를 들어 $S_i = 2$인 관객은 처음에는 앉아 있다가, 일어나서 박수를 치는 사람이 두 명 이상 보이면 그때 일어난다.

당신은 관객 전원의 부끄러움 수치를 알고 있고, 결국 모두가 일어나서 박수를 치도록 프리마돈나의 친구를 객석에 더 초대할 수 있다. 초대하는 친구의 부끄러움 수치는 원하는 값으로 정할 수 있고, 서로 같을 필요는 없다. 기립 박수를 보장하려면 최소 몇 명을 초대해야 하는지 구하라.

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

각 테스트 케이스는 한 줄로 이루어진다. 이 줄에는 객석에서 가장 부끄러움이 많은 사람의 부끄러움 수치 $S_{max}$와 길이가 $S_{max} + 1$인 숫자 문자열이 공백을 사이에 두고 주어진다. 문자열의 $k$번째 숫자는(0부터 센다) 부끄러움 수치가 $k$인 관객의 수이다. 예를 들어 문자열 409는 부끄러움 수치가 0인 관객이 네 명, 2인 관객이 아홉 명 있고 다른 수치의 관객은 없다는 뜻이다. 각 부끄러움 수치의 관객 수는 항상 0명 이상 9명 이하이다.

문자열은 0으로 끝나지 않는다. 즉 객석에는 언제나 한 명 이상이 앉아 있다.

제한

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

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

예제 입력의 테스트 케이스 1에서는 아무도 초대하지 않아도 객석이 스스로 기립 박수를 만든다. 부끄러움 수치가 0인 관객이 먼저 일어나고, 이어서 수치가 1인 관객이 일어나는 식으로 이어진다.

테스트 케이스 2에서는 부끄러움 수치가 0인 친구를 한 명 초대해야 하고, 그 한 명이면 객석 전체가 일어난다.

테스트 케이스 3에서는 부끄러움 수치가 2인 관객 두 명을 추가하는 것이 최적해 중 하나이다.

테스트 케이스 4에서는 관객이 한 명뿐이고 그 관객은 즉시 일어난다. 초대할 친구는 없다.