Tại Nhà Bánh kếp Vô hạn, chỉ có hữu hạn chiếc bánh nhưng có vô hạn thực khách sẵn lòng ăn chúng! Khi nhà hàng mở cửa phục vụ bữa sáng, trong vô hạn thực khách có đúng \(D\) người mang đĩa không rỗng; đĩa thứ \(i\) có \(P_i\) chiếc bánh. Mọi người còn lại có đĩa rỗng.

Thông thường, mỗi phút, mọi thực khách có đĩa không rỗng đều ăn một chiếc bánh trên đĩa mình. Tuy nhiên, một số phút có thể là phút đặc biệt. Trong một phút đặc biệt, quản lý yêu cầu mọi người chú ý, chọn một thực khách có đĩa không rỗng, nhấc một số dương chiếc bánh khỏi đĩa đó và chuyển chúng sang đúng một đĩa khác (đang rỗng hoặc không rỗng). Không ai ăn trong phút đặc biệt, vì làm vậy là bất lịch sự.

Bạn là quản lý trực sáng nay và phải quyết định phút nào, nếu có, là phút đặc biệt, cũng như chuyển bánh nào đi đâu. Nói cách khác, ở mỗi phút bạn hoặc không làm gì để mọi người ăn, hoặc tuyên bố phút đặc biệt và thực hiện đúng một lần chuyển như trên.

Bữa sáng kết thúc khi không còn chiếc bánh nào. Bạn có thể khiến điều đó xảy ra nhanh đến mức nào?

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 \(D\), số thực khách ban đầu có đĩa không rỗng, rồi một dòng chứa \(D\) số nguyên cách nhau bởi dấu cách, là số bánh trên các đĩa đó.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là số phút nhỏ nhất để kết thúc bữa sáng.

Ràng buộc

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

Phân nhóm

• Nhỏ: \(1\le D\le6\), \(1\le P_i\le9\).
• Lớn: \(1\le D\le1000\), \(1\le P_i\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ụ

3
1
3
4
1 2 1 2
1
4

Case #1: 3
Case #2: 2
Case #3: 3

Nguồn

Google Code Jam 2015, Vòng loại, bài Infinite House of Pancakes.

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