2003 Pascal Problem 13

In the diagram, each of the 15 small squares is going to be coloured. Any two squares that have a vertex in common or share a side must be a different colour. What is the *least* number of different colours needed?

\textbf{(A)}\ 3\quad \textbf{(B)}\ 4\quad \textbf{(C)}\ 5\quad \textbf{(D)}\ 8\quad \textbf{(E)}\ 9

If there are no answer choices shown, enter a numerical answer.

Full credit to this problem is given to the CEMC, you may view all Pascal contests here.