Middle European Mathematical Olympiad 2009 Problem T-4

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 queen moves horizontally, vertically or diagonally). Find the maximum $n$, such that for every colouring of the board at least one colour present at the board is connected.