Standing Ovation (Small)

It is opening night at the opera, and your friend is the prima donna, the lead female singer. You will not be in the audience, but you want to make sure she gets a standing ovation, with every audience member standing up and clapping for her.

At the start the entire audience is seated. Every audience member has a shyness level. An audience member with shyness level $S_i$ waits until at least $S_i$ other audience members are already standing and clapping, and once that many are standing she stands up and claps at once. An audience member with $S_i = 0$ always stands up and claps immediately, no matter what anyone else does. For example, an audience member with $S_i = 2$ is seated at the beginning and stands up later, once she sees at least two other people standing and clapping.

You know the shyness level of everyone in the audience, and you can invite more friends of the prima donna into the audience so that the whole crowd ends up standing and clapping. You choose the shyness level of each invited friend, and those levels do not have to be equal. Find the minimum number of friends you must invite to guarantee a standing ovation.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case is one line. The line contains $S_{max}$, the shyness level of the shyest person in the audience, followed by a string of $S_{max} + 1$ single digits, separated by a space. The $k$th digit of the string, counting from 0, is the number of audience members with shyness level $k$. For example, the string 409 means there are four audience members with $S_i = 0$ and nine audience members with $S_i = 2$, and none with any other level. The number of audience members at each shyness level is always between 0 and 9.

The string never ends in a 0, so the audience always holds at least one person.

Limits

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

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of friends you must invite.

In test case 1 of the sample input, the audience produces a standing ovation on its own and you invite nobody. The audience member with shyness level 0 stands up first, then the one with shyness level 1, and so on.

In test case 2, you must invite one friend with shyness level 0, and that single friend is enough to get the whole audience up.

In test case 3, adding two audience members with shyness level 2 is one optimal answer.

In test case 4 there is only one audience member and he stands up immediately, so no friend is needed.