La granja de Peano
Cuando Giuseppe Peano nació en 1858 en una granja, nadie podía sospechar que se convertiría en uno de los grandes matemáticos italianos de la época. Cálculo infinitesimal, axiomatización de las matemáticas, lógica matemática… incluso propuso el uso de un lenguaje universal, interlingua que ha llegado a nuestros días. Una de sus contribuciones más famosas es la llamada curva de Peano con la que mostró que una curva continua puede ser encerrada en una región arbitrariamente pequeña.
En realidad esa curva ya la había utilizado en sus años de adolescencia en la granja familiar. Cuando su padre decidió extender el negocio y comprar vacas, el jóven Giuseppe le propuso colocar los animales de una forma peculiar. Comenzó dividiendo el terreno en parcelas cuadradas (una para cada vaca) organizadas en una especie de rejilla de 3×3. En lugar de conectar todas las parcelas con sus adyacentes abrió las puertas justas para que solo hubiera un camino para ir de cualquier parcela a cualquier otra (el camino completo es una especie de N). El resultado es que para moverse, muchas veces se necesitaba dar un buen rodeo. Por ejemplo para ir desde la (0,2) a la (2,2) hay que atravesar 6 puertas a pesar de que la distancia en línea recta es 2.
Cuando esa distribución se le quedó pequeña (al fin y al cabo solo da para 9 vacas), compró los terrenos al norte y al este triplicando tanto el alto como el ancho del terreno original. Con todo ese nuevo terreno ahora podía tener 3×3 bloques de 3×3 parcelas que organizó para visitarse siguiendo la misma especie de N. Esta vez, eso sí, cada bloque en lugar de ser una parcela para una vaca eran 3×3 parcelas que se recorrían, a su vez, siguiengo la misma especie de N (aunque algunas veces invertida). Con esta disposición para ir desde la celda (1,7) a la (6,7) hay que abrir 51 puertas.
Cuando la granja creció más allá de las 81 vacas que entraban, Peano repitió el mismo proceso. Triplicó el tamaño del terreno tanto a lo ancho como a lo alto y replicó el bloque de 9×9 en 3×3 bloques.
Al final llegó a tener una granja con millones de vacas. Lo peor era trasladarlas de una parcela a otra porque muchas veces el camino se hacía larguísimo.
Entrada
La entrada comienza con una línea con el número de casos de prueba que vendrán a continuación.
Cada caso de prueba consiste en una línea con las coordendas (x1, y1) origen del camino y las coordenadas (x2, y2) destino (el origen y el destino serán siempre distintos). Las coordenadas estarán entre 0 y 319−1.
Salida
Por cada caso de prueba se escribirá una única línea indicando cuántas puertas habrá que abrir para ir desde el origen al destino. Gracias al límite en el ancho y el alto del terreno, se garantiza que ese número nunca superará 263.
Entrada de ejemplo
4 0 2 2 2 2 2 0 2 1 7 6 7 7 1 7 6
Salida de ejemplo
6 6 51 19