Matcom Online Grader

Fitiño, el hermano de Fito, está jugando con un juego de bloques que le compro su hermano mayor. Los bloques de este juego tienen una forma algo extraña como la que se muestra en la figura:

La figura que se muestra es un bloque 3x2, como se puede ver este tiene tres dientes salientes en la partes superior izquierda y tres dientes entrantes en la parte inferior izquierda y a partir del medio de la pieza hay dos dientes salientes en la parte superior y dos dientes en la parte inferior. Es fácil ver que un bloque de este tipo NxM puede ir sobre otro bloque de igual tipo NxM , pero también puede ir sobre un bloque que PxQ donde N >=P y M>=Q . Por lo que nuestra tarea consiste dado un conjunto de bloques saber la cantidad máxima que se puede apilar.

Input

La entrada posee varios casos de prueba, la primera línea de cada caso de prueba es un entero N (1<=N<=10000) que representa la cantidad de bloques, luego en N líneas hay dos números, P y Q separados por un espacio que representan un bloque PxQ (1<=P, Q<=100) . La entrada termina cuando N=0.

Output

Por cada caso de prueba se imprime la mayor cantidad de bloques que se pueden apilar. Cuando se termina la salida se imprime un “ * ”.

Sample test(s)