MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

ACM 2015 - Round #1

Ended

D - Dibujando Rectángulos

Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)

Nuestro amigo Fito también se dedica a las artes plásticas. Recientemente ha estado trabajando en una colección de cuadros muy interesante. En cada cuadro lo que ha hecho Fito es pintar una serie de rectángulos que tienen sus lados paralelos a los del cuadro y sus vértices en coordenadas enteras. Los rectángulos se pueden solapar o contener unos a otros. El lienzo es lo suficientemente grande como para no preocuparnos por sus dimensiones. El problema que tiene Fito es que quiere saber la cantidad final de regiones en las que quedó dividido el cuadro.


Por ejemplo el primer cuadro de la colección de Fito quedó dividido en 8 regiones.


Input

La entrada contiene varios casos de prueba, que representan todos los cuadros de la colección de Fito. Cada caso comienza con un entero $n$ $(1 \le n \le 50)$, que representa la cantidad de rectángulos que Fito pintó. Luego habrá $n$ líneas con 4 enteros $a$, $b$, $x$, $y$ $(0 \le a,b,x,y\le 1000000)$ que representan las coordenadas de cada cuadro, $(a,b)$ es la esquina superior izquierda y $(x,y)$ la esquina inferior derecha.

La entrada se termina con un 0.

Output

Por cada cuadro de la colección de Fito se debe imprimir una línea con un entero que represente la cantidad de regiones en que quedó dividido el mismo.

Sample test(s)

Input
3 4 28 27 11 15 20 42 5 11 24 33 14 5 4 28 27 11 12 11 34 2 7 26 14 16 14 16 19 12 17 28 27 21 2 300000 1000000 600000 0 0 600000 1000000 300000 0
Output
8 6 6