Маленькая девочка Виолетта уже несколько месяцев ходит на кружок по программированию. Недавно она решила, что, как и любой другой программист, она обязательно должна написать игру. В результате ночи разработки к утру получилась игра, которую Виолетта назвала «Miner».

Правила игры довольно просты. Цель игры – поиск мин на двухмерном квадратном поле. Нажав на любой клетке поля правую кнопку мышки, вы размещаете в этой клетке флажок, означающий, что, по вашему мнению, в этой клетке поля находится мина. Нажав левую кнопку мышки, можно открыть клетку, в которой (по вашему мнению) мины нет. Если в этой клетке была мина, то вы проигрываете. В противном случае в клетке либо отображается число от 1 до 8, показывающее, сколько мин находится вокруг данной клетки, либо, если вокруг данной клетки мин нет, открывается не только данная клетка, но и все ещё не открытые соседние. Если среди открывшихся клеток также есть такие, вокруг которых нет ни одной мины, то открываются и все их соседние свободные клетки, и так далее. Цель игры – открыть все свободные клетки поля.

Уже утром Виолетта обнаружила две досадные проблемы. Во-первых, оказывается, очень похожую игру уже написали до нее ;-) А во-вторых, она сама с трудом в неё выигрывает. Подумав, Виолетта решила упростить правила. В новой версии игры положение всех мин известно заранее, а цель игры – открыть все остальные клетки поля, выполнив при этом как можно меньше нажатий левой кнопки мышки.

Так как Виолетта – начинающий программист, то поставленная задача оказалась сложной для нее, поэтому она обратилась к Вам. Помогите Виолетте решить поставленную задачу.