Alice와 Bob은 2차원 $300 \times 300$ 격자판에서 게임을 합니다. 격자판은 여러 칸으로 나뉘어 있으며, 각 칸은 $1$부터 $300$ 사이의 정수인 $(x, y)$ 좌표로 고유하게 식별됩니다.

두 개의 토큰이 서로 다른 칸에 놓여 있습니다. Alice가 먼저 게임을 시작합니다. 각 플레이어는 자신의 차례에 토큰 중 하나를 선택하고, 그 토큰이 위치한 좌표 중 하나를 선택하여 양의 정수만큼 감소시킵니다. 이동하는 토큰은 다른 토큰을 뛰어넘거나 같은 칸에 위치할 수 없습니다. 또한 토큰은 반드시 격자판 내에 있어야 합니다(즉, 두 좌표 모두 양수여야 합니다). 이동할 수 없는 첫 번째 플레이어가 패배합니다. 두 플레이어 모두 두 토큰 중 어느 것이든 이동할 수 있다는 점에 유의하십시오.

여러 게임의 시작 상태가 주어집니다. 각 게임에 대해 Alice가 처음에 둘 수 있는 승리하는 수의 개수를 계산하십시오.

입력

입력의 첫 번째 줄에는 분석할 게임의 수인 정수 $n$ ($1 \le n \le 10^5$)이 주어집니다.

이어지는 $n$개의 줄에는 각각 네 개의 정수 $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2, y_1, y_2 \le 300$이며, $x_1 = x_2$ 또는 $y_1 = y_2$가 성립함)가 주어집니다. 이는 한 게임의 시작 구성을 나타내며, 토큰은 각각 $(x_1, y_1)$과 $(x_2, y_2)$에 위치합니다.

출력

$n$개의 줄을 출력하십시오. 각 줄에는 입력된 각 게임에 대해 Alice가 처음에 둘 수 있는 승리하는 수의 개수를 정수로 출력하십시오. 입력된 순서대로 출력해야 합니다.

예제

입력 1

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

출력 1

3
0
1
1
0