PAML - Popeye and the magical land

As usual Popeye and Brutus are fighting for Olive, and suddenly a witch appears and took Popeye to magical land as Brutus called that witch. In magical land, the witch with her magic make N (1 <= N <= 100) number of clones of Popeye of different strength (0 <= Si <= 100) i.e. each Popeye can hold other Popeyes above his head, and number of Popeyes which can be hold will be less than or equal to strength of Popeye which is holding other Popeyes.

Eg: Imagine there are three Popeyes: the first has strength 2, the second has strength 1 and the third has strength 1. We cannot put the second and the third Popeye simultaneously on the top of the first one. But the second Popeye can place directly on the top of the first one, and then the third Popeye directly on the top of the second one. We will call such construction of Popeye a "Popeye-stack".

The witch want him to make Minimum number of Popeye-stack and give her Maximum Height of Popeye-stack from that arrangement, then only she release him from the magic and give him spinach to defeat Brutus. Help Popeye to get released from the magic of the witch.

Input

First line of Input contains number of test cases T (T <= 1000). Each test case contain two lines: 1st line contains N (1 <= N <= 100) and 2nd line contain N spaced Si (strength of N Popeyes) (0 <= Si <= 100).

Output

For each test case output a string "Case #i: " ("i" is test case number) followed by Minimum number of Popeye-stack and Maximum Height of Popeye-stack separated by a space.

Example

Input:
2
5
0 1 2 3 4
9
0 1 0 2 0 1 1 2 10 Output: Case #1: 1 5
Case #2: 3 4

Added by:P_Quantum
Date:2014-04-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2014-10-25 19:05:05 Julian Waldby
Is one Popeye by himself a Popeye stack of height 1?
2014-06-27 15:33:45 heatOn
Please check my submission I do not know why I am getting WA I have tried generating many test cases and it is working fine on those. And Please specify does the problem statement ask us to find two seperate arrangements such that in the first minimum number of stacks are used and in the second arrangement maximum height of a stack is obtained ?

@Anuj Yadav - U need to find only one arrangement which is having minimum no. of stacks... and in that arrangement which ever is max. height stack i.e maximum height needed.


Last edit: 2014-05-25 17:00:06
2014-06-27 15:33:45 Maru
What do you mean by :"Minimum number of popoye-stack"?

Last edit: 2014-05-12 17:49:14
2014-06-27 15:33:45 BLANKRK
nice one!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.