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

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