The King's Walk

Chess is a game where two sides move pieces and try to capture the opposing king. The pieces differ in how far they travel. Early in a game the king is weak. He moves more slowly than most other pieces and usually hides behind his own pawns. Once both queens have left the board it is time for the king to act. Almost nothing threatens him any more, so he can walk around the board safely, and at this stage his mobility makes him one of the more dangerous pieces. This problem measures that mobility.

The board has $N \times N$ squares and the king is the only piece on it. A square is written as a pair $(X, Y)$ with $1 \le X, Y \le N$. In one move the king steps to a square that touches his current square orthogonally or diagonally, so from $(X, Y)$ he moves to one of the at most eight squares $(X + a, Y + b)$ with $a, b \in \{-1, 0, 1\}$ and $(a, b) \ne (0, 0)$. He may never leave the board.

The king starts on one square and wants to reach another square in as few moves as possible. Count the walks that take him to the destination in that minimum number of moves. Two walks are different if the king stands on a different square after some move.

The first line has an integer $T$, the number of test cases. Each test case is given on two lines.

• One line with a single integer $N$, the size of the board, where $2 \le N \le 5000$.
• One line with four space separated integers $X_1$, $Y_1$, $X_2$, $Y_2$, where $1 \le X_1, Y_1, X_2, Y_2 \le N$. The king starts on $(X_1, Y_1)$ and wants to reach $(X_2, Y_2)$, which is a different square.

For each test case, print one line with a single integer: the number of walks that take the king to the destination in the minimum number of moves, reduced modulo 5318008.