Standing Ovation (Large)

It is opening night at the opera, and your friend sings the prima donna, the lead female role. You will not be in the audience, but you want her to get a standing ovation, meaning every audience member stands up and claps for her.

At the start the whole 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 stands up to clap the moment that happens. An audience member with $S_i = 0$ always stands up and claps right away, no matter what anyone else does. For example, an audience member with $S_i = 2$ is seated at the beginning and stands up later, after seeing at least two other people standing and clapping.

You know the shyness level of everyone in the audience, and you can invite extra friends of the prima donna into the audience so that everyone ends up standing. You may give each invited friend any shyness level you want, and those levels need not be equal. Find the minimum number of friends you have to invite to guarantee a standing ovation.

The first line contains the number of test cases $T$. Each of the following $T$ test cases is one line holding $S_{max}$, the shyness level of the shyest person in the audience, then a space, then a string of $S_{max} + 1$ digits. The $k$th digit of that string (counting from 0) is how many audience members have shyness level $k$. For example, the string "409" means that four audience members have $S_i = 0$ and nine have $S_i = 2$, with nobody at any other level. The number of people 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 1000$

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 case 1 of the first example the audience produces a standing ovation on its own, with no invitation. The member with $S_i = 0$ stands first, then the member with $S_i = 1$ stands, and so on.

In case 2 you must invite one friend with $S_i = 0$, and that is enough to get the whole audience standing.

In case 3 one optimal answer adds two audience members with $S_i = 2$.

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