Левая кнопка мыши

Минер является довольно популярной игрой в операционной системе Windows. Цель игры заключается в поиске мин и маркировании их положения. Вы размещате щелчком правой кнопки мыши небольшой флаг в клетке, в котрой по Вашему мнению расположена мина. Щелчком левой кнопки мыши можно открыть клетку, в которой по Вашему мнению мины нет. Если в этом квадрате все-таки расположена мина, то она взрывается и Вы проигрываете. В противном случае есть два варианта. В первом случае открывается число от 1 до 8, показывающее суммарное количество мин, окружающих данную клетку. Например, если Вы нажали левую кнопку мыши и в квадрате высветилось число 8, то это означает, что данная клетка окружена 8 клетками с минами, т.е все 8 соседних клеток содержат мины. Во втором случае, если вокруг этой клетки нет соседних мин, то кроме этой клетки открываются и все соседние. Если в каких-то из соседних клеток также нет окружающих мин, то процесс открытия соседних клеток продолжается. То есть фактически компьютер помогает Вам открыть все свободные от мин соседние клетки. Цель игры состоит в открыти всех свободных от мин клеток. Том очень увлеается этой игрой, но к сожалению его правая кнопка мыши повреждена и он может пользоваться только левой кнопкой мыши. Для того чтобы избежать возможного дальнейшего повреждения мыши он хочет закончить игру нажав на левую кнопку мыши минимальное количество раз. Зная начальное положение в игре Вам необходимо определить это самое минимальное количество нажатий левой кнопкой мыши.

Входные данные

Первая строка содержит целое число, указывающее количество тестовых случаев T (T ≤ 12). Каждый тестовый случай начинается строкой, содержащей целое число n (5 ≤ n ≤ 9) - размер минного поля n×n. Каждая из последующих n строк содержит по n символов M_ij(1 ≤ i, j ≤ n), M_ij обозначает текущий статус клетки в строке i и столбце j, где '@' обозначает мину, '0-8' обознают сумарные количества мин в прилегающих клетках, цифрой '0' обозначены клетки, по соседству с которыми мин нет. Гарантируется, что все положения корректны.

Выходные данные

Для каждого тестового случая в отдельной строке вывести сообщение о номере теста (начиная с 1) и далее минимальное количество нажатий левой кнопки мыши (см. пример выходных данных).