SMO 2008 Problem 5

consider a $2008 \times 2008$ chess board. let $M$ be the smallest no of rectangles that can be drawn on the chess board so that sides of every cell of the board is contained in the sides of one of the rectangles. find the value of $M$ . (eg for $2\times 3$ chessboard, the value of $M$ is 3.)