개미 탑

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

오늘 Scott은 개미들에게 도전 과제를 주기 위해 개미 농장의 꼭대기에 먹이를 놓았다. 개미들은 수직으로 탑을 쌓아 먹이에 도달하려 하며, 탑의 각 개미는 바로 다음 개미를 등에 직접 받친다. 이 방식으로 각 개미는 자기 위에 있는 모든 개미의 무게를 견딘다. Scott의 개미들은 몸집에 비해 매우 강해서 자기 무게의 최대 6배까지 들 수 있다. 예를 들어, 무게가 8밀리그램인 개미는 각각 24밀리그램인 다른 개미 두 마리를 들 수 있다! 각 개미는 몸길이도 가지며, 모든 길이가 서로 다르다는 점을 제외하면 정확한 길이는 중요하지 않다.

• 탑은 일렬이어야 한다. 맨 위의 개미를 제외한 각 개미는 정확히 한 마리의 개미 바로 아래에 있어야 하며, 맨 아래의 개미를 제외한 각 개미는 정확히 한 마리의 개미 바로 위에 있어야 한다.

• 탑에 있는 개미들의 길이는 탑의 아래에서 위로 갈수록 엄격하게 감소해야 한다. 이렇게 해야 탑에 새로 합류하는 각 개미가 꼭대기까지 기어 올라갈 수 있다.

• 각 개미에 대해, 탑에서 그 개미 위에 있는 모든 개미의 무게 합은 그 개미 무게의 6배 이하여야 한다.

이 개미들 중 이러한 탑을 만들 수 있는 개미의 최대 수는 얼마인가?

제한

7 ≤ T ≤ 100. 시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

정확히 6개의 경우에는 N = 100이고, 나머지 T - 6개의 경우에는 2 ≤ N ≤ 50. 모든 i에 대해 1 ≤ $W_{i}$ ≤ 1000.

테스트 세트 2 (비공개)

정확히 6개의 경우에는 N = $10^{5}$이고, 나머지 T - 6개의 경우에는 2 ≤ N ≤ 500. 모든 i에 대해 1 ≤ $W_{i}$ ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 군집에 있는 개미의 수를 나타내는 정수 N이 적힌 한 줄로 시작한다. 그다음 두 번째 줄에 N개의 정수 $W_{1}$, $W_{2}$, ..., $W_{N}$가 주어지며, 여기서 $W_{i}$는 i번째 개미의 무게를 밀리그램 단위로 나타낸다. 개미들은 길이가 엄격하게 증가하는 순서로 나열된다. 실제 길이 값은 주어지지 않으며 순서만 중요하다는 점에 유의한다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 주어진 개미들 중 위의 규칙을 따르는 탑을 만들 수 있는 개미의 최대 수이다.

예제 케이스 #1에는 개미가 두 마리 있다. 첫 번째 개미의 무게는 9 mg이고, 두 번째 개미의 무게는 1 mg이며 첫 번째 개미보다 길다. 첫 번째 개미는 두 번째 개미를 들 만큼 강하지만(최대 9 × 6 mg까지 들 수 있으므로), 두 번째 개미가 더 길기 때문에 들 수 없다. 두 번째 개미는 첫 번째 개미를 들 만큼 강하지 않다(최대 1 × 6 mg까지만 들 수 있으며, 이는 9 mg보다 작기 때문이다). 따라서 두 개미 중 한 마리만으로 이루어진 "탑"만 만들 수 있다.

예제 케이스 #2에서는 세 개미 모두가 탑을 만들 수 있으며, 세 번째 개미가 두 번째 개미를 받치고 두 번째 개미가 첫 번째 개미를 받친다.

예제 케이스 #3에서 최적해는 아홉 번째 개미를 맨 아래에 놓고, 그 위에 다른 개미 일곱 마리를 놓는다.