题目描述

Alice and Bob are playing a game on board which is a 2-dimensional $300 \times 300$ grid. The board is subdivided into cells. Each cell can be uniquely identified by two integers representing $(x, y)$ coordinates, each in the range from $1$ to $300$.

Two tokens are on the board on distinct cells. Alice starts the game. On each player’s turn, that player chooses one of the tokens, chooses one of the coordinates of the cell it’s on, and reduces that coordinate by some positive amount. The moved token cannot jump over or occupy the same space as the other token. The token must also remain on the board (so both of its coordinates need to stay positive). The first player unable to make a move loses. Note that both players can move either token.

You are given the starting configuration of a number of games. For each of the games, compute the number of initial winning moves available to Alice.

输入格式

The first line of input contains a single integer $n$ ($1 \le n \le 10^5$), which is the number of games to analyze.

Each of the next $n$ lines contains four integers $x_1$, $y_1$, $x_2$ and $y_2$ ($1 \le x_1, x_2, y_1, y_2 \le 300$, and either $x_1 \ne x_2$ or $y_1 \ne y_2$ holds). This represents the starting configuration of one game, with the tokens at cells $(x_1, y_1)$ and $(x_2, y_2)$.

输出格式

Output $n$ lines. On each line, output a single integer, which is the number of initial winning moves available to Alice for one of the input games. Output them in the order of the input.

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

3
0
1
1
0