Alice y Bob están jugando un juego en un tablero que es una cuadrícula bidimensional de $300 \times 300$. El tablero está subdividido en celdas. Cada celda puede ser identificada de forma única por dos números enteros que representan las coordenadas $(x, y)$, cada una en el rango de 1 a 300.

Hay dos fichas en el tablero en celdas distintas. Alice comienza el juego. En el turno de cada jugador, ese jugador elige una de las fichas, elige una de las coordenadas de la celda en la que se encuentra y reduce esa coordenada en una cantidad positiva. La ficha movida no puede saltar sobre la otra ficha ni ocupar el mismo espacio que ella. La ficha también debe permanecer dentro del tablero (por lo que ambas coordenadas deben seguir siendo positivas). El primer jugador que no pueda realizar un movimiento pierde. Tenga en cuenta que ambos jugadores pueden mover cualquiera de las dos fichas.

Se le proporciona la configuración inicial de varios juegos. Para cada uno de los juegos, calcule el número de movimientos iniciales ganadores disponibles para Alice.

Entrada

La primera línea de la entrada contiene un único número entero $n$ ($1 \le n \le 10^5$), que es el número de juegos a analizar.

Cada una de las siguientes $n$ líneas contiene cuatro números enteros $x_1, y_1, x_2$ y $y_2$ ($1 \le x_1, x_2, y_1, y_2 \le 300$, y se cumple que $x_1 = x_2$ o $y_1 = y_2$). Esto representa la configuración inicial de un juego, con las fichas en las celdas $(x_1, y_1)$ y $(x_2, y_2)$.

Salida

Imprima $n$ líneas. En cada línea, imprima un único número entero, que es el número de movimientos iniciales ganadores disponibles para Alice para uno de los juegos de entrada. Imprímalos en el orden de la entrada.

Ejemplos

Entrada 1

5
6 6 6 3
6 6 2 2
1 6 3 1
3 6 1 3
6 3 1 5

Salida 1

3
0
1
1
0