Scott có một trại kiến gồm \(N\) con. Mỗi con kiến có một chiều dài và cân nặng nhất định.

Hôm nay, để thử thách đàn kiến, Scott đặt thức ăn ở trên cao trong trại. Đàn kiến cố với tới bằng cách xếp thành một chồng thẳng đứng, mỗi con trong chồng trực tiếp đỡ con kế tiếp trên lưng. Như vậy, mỗi con phải chịu tổng cân nặng của tất cả kiến phía trên nó. Kiến của Scott rất khỏe so với kích thước: mỗi con mang được tối đa 6 lần cân nặng của chính nó. Chẳng hạn, một con nặng 8 miligam có thể mang hai con khác, mỗi con nặng 24 miligam! Mỗi con còn có chiều dài cơ thể; giá trị chiều dài cụ thể không quan trọng, chỉ biết tất cả chúng khác nhau.

Chồng kiến phải là một đường thẳng: trừ con trên cùng, mỗi con nằm trực tiếp dưới đúng một con; trừ con dưới cùng, mỗi con nằm trực tiếp trên đúng một con. Chiều dài phải giảm nghiêm ngặt từ đáy lên đỉnh, để mỗi con mới tham gia có thể bò lên trên cùng. Với mỗi con, tổng cân nặng của mọi con phía trên không được vượt quá 6 lần cân nặng của nó.

Nhiều nhất bao nhiêu con kiến có thể tạo thành một chồng như vậy?

Dữ liệu vào

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

Mỗi bộ test bắt đầu bằng một dòng chứa \(N\), số kiến trong đàn. Dòng tiếp theo chứa \(N\) số nguyên \(W_1,W_2,\ldots,W_N\), trong đó \(W_i\) là cân nặng tính bằng miligam của con thứ \(i\). Các con được liệt kê theo thứ tự chiều dài tăng nghiêm ngặt. Đề không cho giá trị chiều dài thực; chỉ thứ tự này là quan trọng.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là số kiến lớn nhất có thể tạo thành một chồng tuân thủ các quy tắc trên.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Hiển thị): đúng 6 bộ test có \(N=100\); với \(T-6\) bộ còn lại, \(2\le N\le50\). Với mọi \(i\), \(1\le W_i\le1000\).
• Test Set 2 (Ẩn): đúng 6 bộ test có \(N=10^5\); với \(T-6\) bộ còn lại, \(2\le N\le500\). Với mọi \(i\), \(1\le W_i\le10^9\).

Đ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
2
9 1
3
8 4 100
9
10 10 10 10 10 10 10 10 100

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

Nguồn

Google Code Jam 2018, Vòng 1C, bài Ant Stack.

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