K. King Game
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice and Bob are playing a cool new game called "King Game." The King Game consists of a $$$300 \times 300$$$ board and two pieces that can be placed on certain positions on the board. For convenience, we use 2D coordinates $$$(x, y)$$$ to represent the positions where pieces are placed, where $$$1 \leq x, y \leq 300$$$.

The rules of the King Game are as follows:

  • At the start of the game, the two pieces are placed on different positions: $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.
  • The players take turns to move, and each turn, the player must choose one of the pieces. Suppose the position of the chosen piece is $$$(x, y)$$$, the player can move it to any position $$$(p, q)$$$ such that $$$1\leq p \leq x$$$ and $$$1\leq q \leq y$$$. However, the new position $$$(p, q)$$$ cannot be $$$(x, y)$$$ or coincide with another piece.
  • The player who cannot make a move loses.

Alice and Bob are going to play $$$T$$$ games, and they have already planned the starting coordinates for each game. Can you tell them, for each game, how many winning first moves the "first player" has under the condition that both players play optimally?

Input

The first line contains a positive integer $$$T$$$, representing the number of games.

The next $$$T$$$ lines each contain four integers $$$x_1, y_1, x_2, y_2$$$, representing the starting coordinates of the pieces for one game.

  • $$$1 \leq T \leq 10^5$$$
  • $$$1 \leq x_1, y_1, x_2, y_2 \leq 300$$$
  • It is guaranteed that for each game, $$$x_1 \neq y_1$$$ or $$$x_2 \neq y_2$$$.
Output

For each game, output a single integer on a new line representing the number of winning first moves the first player has.

Example
Input
5
1 2 3 4
3 1 4 2
6 6 2 2
3 2 2 3
1 12 3 9
Output
1
2
2
0
0