On a $999\times 999$ board a [i]limp rook[/i] can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A [i]non-intersecting route[/i] of the limp rook consists of a sequence of pairwise different squares that the limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting route is called [i]cyclic[/i], if the limp rook can, after reaching the last square of the route, move directly to the first square of the route and start over. 
How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit?

[i]Proposed by Nikolay Beluhov, Bulgaria[/i]
To solve the problem, we need to determine the longest possible cyclic, non-intersecting route of a limp rook on a \(999 \times 999\) board. We will generalize the solution for an \(n \times n\) board where \(n \equiv 3 \pmod{4}\) and \(n \geq 7\).

1. **Proof of Lower Bound:**
   We first show that \(n^2 - 2n - 3\) is achievable. Consider the construction for \(n = 15\):

   ![Board Construction](https://i.imgur.com/7Z5Q5kG.png)

   The route of the limp rook forms a "snake" that coils around the board, leaving only a \(3 \times 3\) square unfilled. Furthermore, the two ends of the snake each leave 2 squares unfilled, and each turn of the snake leaves 4 squares unfilled.

   This construction leaves a total of \(2n + 3\) squares unfilled, as desired.

2. **Proof of Upper Bound:**
   We now prove that \(n^2 - 2n - 3\) is maximal. Color the squares in the grid as follows:

   ![Colored Grid](https://i.imgur.com/7Z5Q5kG.png)

   Let \(R\) denote the color red, and so on. The sequence of colors on the route of the limp rook must repeat in the pattern:
   \[
   R, Y, B, G, R, Y, B, G, \ldots
   \]
   (or the above sequence reversed). It follows that the length of the sequence is \(4T\), where \(T\) is the number of blue squares on the limp rook's route.

   **Claim:** The limp rook cannot pass through all the blue squares.

   *Proof:* Assume for contradiction that the limp rook passes through all the blue squares. Say two blue squares are *consecutive* if the limp rook visits them without visiting any other blue square in between. Note that two consecutive blue squares must be either orthogonally adjacent or diagonally adjacent.

   Checkerboard color the blue squares periwinkle and navy blue. Since there is an odd number of blue squares, the number of periwinkle squares and the number of navy blue squares are unequal. Thus, there is at least one pair of diagonally adjacent consecutive blue squares.

   ![Checkerboard](https://i.imgur.com/7Z5Q5kG.png)

   Without loss of generality, the limp rook moves:
   \[
   (a, b+2) \to (a+1, b+2) \to (a+1, b+1) \to (a+2, b+1) \to (a+2, b)
   \]
   Then, since the limp rook must move in the pattern \(R, Y, B, G, \ldots\), at some point in the sequence the limp rook moves:
   \[
   (a+2, b+3) \to (a+2, b+2) \to (a+3, b+2)
   \]
   Then the rook must eventually move from \((a+2, b)\) to \((a+2, b+3)\) and \((a+3, b+2)\) to \((a, b+2)\). It is clear these two paths must intersect, contradiction. \(\blacksquare\)

   Hence, the length of the limp rook's route is at most:
   \[
   4 \left[ \left( \frac{n-1}{2} \right)^2 - 1 \right] = n^2 - 2n - 3
   \]
   and we are done.

The final answer is \( \boxed{ 996000 } \).