We colour every square of the
![2009 \times 2009](/media/m/2/e/5/2e531eb46f5e67ce4bf3c9bffe24957b.png)
board with one of
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
colours (we do not have to use every colour). A colour is called connected if either there is only one square of that colour or any two squares of the colour can be reached from one another by a sequence of moves of a chess queen without intermediate stops at squares having another colour (a chess quen moves horizontally, vertically or diagonally). Find the maximum
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
, such that for every colouring of the board at least on colour present at the board is connected.
%V0
We colour every square of the $2009 \times 2009$ board with one of $n$ colours (we do not have to use every colour). A colour is called connected if either there is only one square of that colour or any two squares of the colour can be reached from one another by a sequence of moves of a chess queen without intermediate stops at squares having another colour (a chess quen moves horizontally, vertically or diagonally). Find the maximum $n$, such that for every colouring of the board at least on colour present at the board is connected.