Under construction

Still being built. Things may change

Ant Stack

Interview

Time limit15sMemory limit1024 MB

Summary
Given ants listed by increasing length with their weights, find the largest stack where each ant carries at most 6 times its own weight above it.
Level

Medium5 of 10

Topics
Dynamic programming, Greedy
Solved
No attempts yet

Problem

Scott has an ant farm containing N ants. Each ant has a certain length and weight.

Today, as a challenge for the ants, Scott has placed some food at the top of the ant farm. The ants will try to reach it by arranging themselves into a vertical stack, with each ant directly holding the next one on its back. Each ant therefore bears the weight of all ants above it.

Scott's ants are very strong for their size and can carry up to 6 times their own weight. For example, an ant that weighs 8 milligrams can carry two other ants weighing 24 milligrams each. Each ant also has a body length. The exact lengths do not matter, except that they are all different.

The stack must follow these rules:

  • The stack must be linear. Each ant except the top ant is directly below exactly one ant, and each ant except the bottom ant is directly above exactly one ant.
  • Lengths strictly decrease from bottom to top. This way, each new ant that joins the stack can climb to the top.
  • For each ant, the total weight of all ants above it must be no more than 6 times its own weight.

What is the maximum number of these ants that can form such a stack?

Input

The first line gives the number of test cases, T. T test cases follow. Each test case begins with a line containing an integer N, the number of ants in the colony. The next line contains N integers W1, W2, ..., WN, where Wi is the weight in milligrams of the i-th ant. The ants are listed in strictly increasing order of length. No actual length values are given, only their order matters.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of the given ants that can form a stack that obeys the rules above.

Constraints

7 ≤ T ≤ 100.

Hint

In sample case 1, there are two ants. The first weighs 9 mg, and the second weighs 1 mg and is longer than the first. The first ant is strong enough to hold the second (it can hold up to 9 × 6 mg), but the second ant is longer, so they cannot be stacked. The second ant can only hold up to 1 × 6 mg, which is less than 9 mg, so it cannot hold the first ant either. Only a stack of one ant is possible.

In sample case 2, all three ants can form a stack. The third ant holds the second, and the second holds the first.

In sample case 3, the optimal stack has the ninth ant at the bottom, with seven of the other ants above it.

Examples1

  1. Example 1

    Input
    3
2
9 1
3
8 4 100
9
10 10 10 10 10 10 10 10 100
    Expected output
    Case #1: 1
Case #2: 3
Case #3: 8