개미 스택

Scott은 개미 N마리가 들어 있는 개미 농장을 가지고 있다. 각 개미는 일정한 길이와 무게를 가진다.

오늘 Scott은 개미들에게 도전 과제로 농장 맨 위에 먹이를 놓았다. 개미들은 각자 등 위에 다음 개미를 업는 방식으로 수직 스택을 만들어 먹이에 도달하려 한다. 따라서 각 개미는 자기 위에 있는 모든 개미의 무게를 버틴다.

Scott의 개미는 몸집에 비해 매우 강해서 자기 무게의 최대 6배까지 버틸 수 있다. 예를 들어 무게가 8 mg인 개미는 무게가 24 mg인 개미 두 마리를 버틸 수 있다. 각 개미에는 몸 길이도 있다. 모든 개미의 길이가 서로 다르다는 점 외에는 정확한 길이 값은 중요하지 않다.

스택은 다음 규칙을 따라야 한다.

• 스택은 일직선이어야 한다. 맨 위 개미를 제외한 각 개미는 바로 위에 정확히 한 마리가 있고, 맨 아래 개미를 제외한 각 개미는 바로 아래에 정확히 한 마리가 있어야 한다.
• 아래에서 위로 갈수록 길이가 엄격하게 줄어든다. 그래야 새로 합류하는 개미가 꼭대기까지 올라갈 수 있다.
• 각 개미에 대해, 그보다 위에 있는 모든 개미의 무게 합은 그 개미 무게의 6배를 넘을 수 없다.

이 조건을 만족하는 스택을 만들 수 있는 개미의 최대 수는 몇 마리인가?

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 개미 수 N이 적힌 줄로 시작한다. 다음 줄에는 N개의 정수 W1, W2, ..., WN이 주어진다. Wi는 i번째 개미의 무게(mg)이다. 개미들은 길이가 엄격하게 증가하는 순서로 나열되어 있다. 실제 길이 값은 주어지지 않으며, 순서만 중요하다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 위 규칙을 지키는 스택을 만들 수 있는 주어진 개미의 최대 수이다.

7 ≤ T ≤ 100

샘플 케이스 1에는 개미가 두 마리 있다. 첫 번째 개미는 무게가 9 mg이고, 두 번째 개미는 무게가 1 mg이며 첫 번째 개미보다 길다. 첫 번째 개미는 9 × 6 mg까지 버틸 수 있어 두 번째 개미를 감당할 수 있지만, 두 번째 개미가 더 길어서 쌓을 수 없다. 두 번째 개미는 최대 1 × 6 mg까지만 버틸 수 있어 첫 번째 개미를 버틸 수 없다. 따라서 개미 한 마리로만 스택을 만들 수 있다.

샘플 케이스 2에서는 세 마리 모두 스택을 이룰 수 있다. 세 번째 개미가 두 번째 개미를, 두 번째 개미가 첫 번째 개미를 받친다.

샘플 케이스 3에서 최적의 스택은 아홉 번째 개미를 맨 아래에 두고, 그 위에 나머지 개미 중 일곱 마리를 올리는 것이다.