teddy online judge

43. La Torre de Babel

Limite de tiempo : 1 seg.   Total runs : 32  Aceptados : 2

En la torre de Babel
vivían cincuenta cigarros
vivían amontonados
hechos todos de papel
— Los Tres, La Torre de Babel

Se encuentra ante ti una inmensa caja con muchísimos bloques de LEGO, cada uno de un color diferente. Recordando buenos tiempos, unes varias piezas todos para formar una altísima torre. Mientras la construyes, y para dar mayor estabilidad, te vas cerciorando de que al colocar una pieza sobre otra, la de arriba debe estar completamente cubierta por la de abajo (esto es, W_i ≥ W_i+1 y H_i ≥ H_i+1), pero hay que tomar en cuenta que puedes rotar las piezas 90°. Pronto terminas la torre, pero una pregunta se queda en tu cabeza: ¿Cuántas torres distintas pudiste haber construído? Una torre se define como una o más piezas apiladas verticalmente. Dos torres se consideran distintas si sus alturas son diferentes o si el orden de los colores cambia.

Input

La primer línea de la entrada contiene un único número, N, el número de casos de prueba que siguen. Cada caso de prueba consiste de una línea con 1 número, p (1 ≤ p ≤ 1000), el número de piezas. Después vienen p líneas con dos números cada una W_i y H_i, (1 ≤ W_i, H_i ≤ 1000) que representan el ancho y el alto de la i-ésima pieza.

Output

Para cada caso, debes imprimir una línea "Caso c: n", siendo c el número secuencial del caso y n los últimos 5 dígitos del número de torres distintas que se pueden formar con esas piezas.

Sample Input/Output