Đêm khai mạc opera đã đến, và bạn của bạn là prima donna (nữ ca sĩ chính). Bạn không có mặt trong khán phòng, nhưng muốn chắc chắn rằng cô ấy nhận được một màn đứng dậy vỗ tay: mọi khán giả đều đứng lên và vỗ tay cho cô.

Ban đầu, toàn bộ khán giả đều ngồi. Mỗi người có một mức độ e ngại. Người có mức \(S_i\) sẽ chờ cho đến khi ít nhất \(S_i\) khán giả khác đã đứng dậy vỗ tay; ngay khi điều đó xảy ra, người ấy cũng lập tức đứng lên vỗ tay. Nếu \(S_i=0\), người ấy luôn đứng dậy ngay, bất kể những người khác làm gì. Chẳng hạn, người có \(S_i=2\) vẫn ngồi lúc đầu, nhưng sẽ đứng lên sau khi thấy ít nhất hai người khác đang đứng và vỗ tay.

Bạn biết mức độ e ngại của tất cả khán giả và sẵn sàng mời thêm bạn của prima donna để cuối cùng cả khán phòng đều đứng lên. Mỗi người bạn được mời có thể mang bất kỳ mức độ e ngại nào bạn muốn, không nhất thiết giống nhau. Hỏi cần mời ít nhất bao nhiêu người để bảo đảm có một màn đứng dậy vỗ tay?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi test gồm một dòng chứa \(S_{max}\), mức lớn nhất của người e ngại nhất trong khán phòng, tiếp theo là một chuỗi gồm \(S_{max}+1\) chữ số. Chữ số thứ \(k\) của chuỗi (đếm từ 0) là số khán giả có mức e ngại \(k\). Ví dụ, 409 nghĩa là có bốn người với \(S_i=0\), chín người với \(S_i=2\), và không có ai với \(S_i=1\) hay mức nào khác. Ban đầu luôn có từ 0 đến 9 người ở mỗi mức.

Chuỗi không bao giờ kết thúc bằng 0; do đó khán phòng luôn có ít nhất một người.

Dữ liệu ra

Với mỗi test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự test (bắt đầu từ 1) và \(y\) là số bạn ít nhất phải mời.

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Nhỏ: \(0\le S_{max}\le6\).
• Lớn: \(0\le S_{max}\le1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
4 11111
1 09
5 110011
0 1

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 0

Nguồn

Google Code Jam 2015, Vòng loại, bài Standing Ovation.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.