Alice et Bob jouent à un jeu sur un plateau qui est une grille bidimensionnelle de $300 \times 300$. Le plateau est subdivisé en cellules. Chaque cellule peut être identifiée de manière unique par deux entiers représentant des coordonnées $(x, y)$, chacune comprise entre 1 et 300.

Deux jetons sont placés sur le plateau sur des cellules distinctes. Alice commence la partie. À chaque tour, le joueur choisit l'un des jetons, choisit l'une des coordonnées de la cellule sur laquelle il se trouve, et réduit cette coordonnée d'une certaine valeur positive. Le jeton déplacé ne peut pas sauter par-dessus l'autre jeton ni occuper la même case que lui. Le jeton doit également rester sur le plateau (les deux coordonnées doivent donc rester positives). Le premier joueur incapable d'effectuer un mouvement perd. Notez que les deux joueurs peuvent déplacer l'un ou l'autre des jetons.

On vous donne la configuration initiale d'un certain nombre de parties. Pour chacune de ces parties, calculez le nombre de coups gagnants initiaux disponibles pour Alice.

Entrée

La première ligne de l'entrée contient un entier unique $n$ ($1 \le n \le 10^5$), qui est le nombre de parties à analyser.

Chacune des $n$ lignes suivantes contient quatre entiers $x_1, y_1, x_2$ et $y_2$ ($1 \le x_1, x_2, y_1, y_2 \le 300$, et soit $x_1 = x_2$, soit $y_1 = y_2$ est vérifié). Cela représente la configuration initiale d'une partie, avec les jetons aux cellules $(x_1, y_1)$ et $(x_2, y_2)$.

Sortie

Affichez $n$ lignes. Sur chaque ligne, affichez un entier unique, qui est le nombre de coups gagnants initiaux disponibles pour Alice pour l'une des parties données. Affichez-les dans l'ordre de l'entrée.

Exemples

Entrée 1

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

Sortie 1

3
0
1
1
0