킹의 행마

체스는 두 편이 말을 움직여 상대의 킹을 잡으려는 경기다. 말마다 움직이는 범위가 다르다. 경기 초반의 킹은 약하다. 다른 말보다 느리게 움직이고, 대개 자기 폰 뒤에 숨어 있다. 양쪽 퀸이 판에서 사라지면 킹이 나설 때가 된다. 킹을 위협할 말이 거의 남지 않아 판 위를 안전하게 돌아다닐 수 있고, 이 단계의 킹은 기동력이 좋아 오히려 위험한 말 중 하나가 된다. 이 문제는 그 기동력을 잰다.

$N \times N$ 칸으로 이루어진 체스판이 있고, 판 위의 말은 킹 하나뿐이다. 각 칸은 $1 \le X, Y \le N$인 좌표 $(X, Y)$로 나타낸다. 킹은 한 번에 가로, 세로, 대각선으로 맞닿은 칸으로 움직인다. 즉 $(X, Y)$에서 $a, b \in \{-1, 0, 1\}$이고 $(a, b) \ne (0, 0)$인 칸 $(X + a, Y + b)$ 최대 여덟 개 중 하나로 갈 수 있다. 판 밖으로는 나갈 수 없다.

킹은 한 칸에서 출발해 다른 한 칸까지 가능한 한 적은 횟수로 이동하려고 한다. 최소 이동 횟수로 목적지에 도착하는 경로가 몇 가지인지 세어라. 어떤 이동 뒤에 킹이 서 있는 칸이 다르면 서로 다른 경로다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

• 첫 줄에 판의 크기 $N$이 주어진다. $2 \le N \le 5000$이다.
• 둘째 줄에 네 정수 $X_1$, $Y_1$, $X_2$, $Y_2$가 공백으로 구분되어 주어진다. $1 \le X_1, Y_1, X_2, Y_2 \le N$이다. 킹은 $(X_1, Y_1)$에서 출발해 $(X_2, Y_2)$로 가려고 하며, 두 칸은 서로 다르다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 킹이 최소 이동 횟수로 목적지에 도착하는 경로의 수를 5318008로 나눈 나머지다.