teddy online judge

27. Cajas

Limite de tiempo : 1 seg.   Total runs : 295  Aceptados : 102

El encargado de “Empresa Productora de Cartón” decidió lanzar una línea nueva de cajas. La línea consiste en una colección de cajas cúbicas de diferentes tamaños. Como promoción de lanzamiento se hicieron paquetes de cajas de tal forma que al abrir una puedas encontrar otra y dentro de ésta una más y así sucesivamente hasta abrir la caja más pequeña incluida en el paquete. De improviso llega un cliente a la fábrica pidiendo un paquete de lanzamiento; desafortunadamente todos los paquetes ya fueron enviados a las tiendas. Dado que tú eres el responsable de armarlos decides formar uno con el mayor núemero posible de cajas existentes en la fábrica. Debes hacer un programa que lea el tamaño de cada una de las cajas que hay en la fábrica y escriba el mayor número de cajas que puede tener el paquete. Dentro de una caja de tamaño T puedes meter otra de tamaño t sólo si t < T.

Entrada

La primer línea de entrada contendrá un sólo número entero n (1 ≤ n ≤ 100). Dicho número representa el número de casos de prueba para este problema. Cada una de las sigueintes n líneas describirá un caso de prueba. En cada caso debes de leer primero un entero k (1 ≤ k ≤ 1000) que indica cuántas cajas hay en la fábrica y después leer el tamaño de cada una de las k cajas. El tamaño de cada caja será un entero entre 1 y 50.

Salida

Para caso de prueba debes escribir una línea de texto con el mensaje “Caso k: N cajas.”, siendo N el número de cajas en el paquete más grande y k el número del caso de prueba.

Entrada y salida de prueba

4
11 1 2 3 4 5 6 7 8 9 10 11
1 10
4 2 2 2 2
5 1 2 2 3 10

Caso 1: 11 cajas.
Caso 2: 1 cajas.
Caso 3: 1 cajas.
Caso 4: 4 cajas.