MEMO 2009 Problem 8

We colour every square of the $2009$ x $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.