TUYMAADA 2006 Problem 7

From a $n\times (n-1)$ rectangle divided into unit squares, we cut the corner, which consists of the first row and the first column. (that is, the corner has $2n-2$ unit squares). For the following, when we say corner we reffer to the above definition, along with rotations and symmetry. Consider an infinite lattice of unit squares. We will color the squares with $k$ colors, such that for any corner, the squares in that corner are coloured differently (that means that there are no squares coloured with the same colour). Find out the minimum of $k$ .

Proposed by S. Berlov