IMO 2009 — Toàn bộ Shortlist Câu hỏi 13

Trên bàn cờ $999 \times 999$, một quân xe khập khiễng được phép đi từ một ô tới ô kề có chung cạnh. Mỗi bước phải là một lần rẽ: hướng của hai bước liên tiếp vuông góc nhau. Một đường đi không tự cắt là dãy các ô đôi một khác nhau mà quân xe có thể đi qua theo thứ tự bằng các nước đi hợp lệ. Đường đi được gọi là tuần hoàn nếu từ ô cuối, quân xe có thể đi thẳng về ô đầu rồi tiếp tục lặp lại.

Đường đi tuần hoàn, không tự cắt dài nhất của quân xe đi qua bao nhiêu ô?