Олимпиада Туймаада по математике. Старшая лига. 2006 год

Из картонного клетчатого прямоугольника $n\times (n-1)$ вырезан уголок, состоящий из всех клеток первой строки и первого столбца (всего в нем $2n-2$ клетки). Клетки бесконечной клетчатой плоскости покрашены в $k$ цветов так, что при любом положении картонного уголка на этой плоскости (с учетом поворотов и переворотов) все покрытые им клетки имеют разный цвет. При каком наименьшем $k$ это возможно? ( С. Берлов )