5-я Международная Жаутыковская олимпиада, 2009 год

В клетчатом квадрате $17\times 17$ $n$ клеток окрашены в черный цвет. Назовем линией любой столбец, любую строку и любую из двух диагоналей квадрата. За один шаг, если в некоторой линии есть хотя бы 6 черных клеток, можно окрасить все ее клетки в черный цвет.
Найдите наименьшее такое $n$, что при некотором расположении исходных $n$ черных клеток можно за несколько шагов окрасить все клетки квадрата.