Олимпиадный тренинг

Задача . D. Я люблю 1543

Задача

Однажды утром Поликарп проснулся и понял: $1543$ — самое любимое число в его жизни.

Первым же, что Поликарп в этот день увидел, как только открыл глаза, был большой настенный ковёр из $n$ на $m$ клеток, $n$ и $m$ — чётные. Каждая клетка содержит одну из цифр от $0$ до $9$.

Поликарпу стало интересно, сколько всего раз встретится запись числа $1543$ во всех слоях$^{\text{∗}}$ ковра при его обходе по часовой стрелке.

$^{\text{∗}}$Первым слоем ковра размеров $n \times m$ называют замкнутую ленту длиной $2 \cdot (n+m-2)$ и толщиной в $1$ элемент, ограничивающую его внешнюю часть. Каждый следующий слой определяется как первый слой ковра, полученного путём удаления всех предыдущих слоёв из исходного ковра.

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

Первая строка входных данных содержит одно целое число $t$ ($1 \leq t \leq 100$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит пару чисел $n$ и $m$ ($2 \leq n, m \leq 10^3$, $n, m$ — чётные).

После этого следует $n$ строк длины $m$, состоящих из цифр от $0$ до $9$ — описание ковра.

Гарантируется, что сумма $n \cdot m$ по всем наборам входных данных не превосходит $10^6$.

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

Для каждого набора выведите единственное число — суммарное количество раз, которое $1543$ встречается во всех слоях ковра в порядке обхода по часовой стрелке.

Примечание

$\text{[math]}$ Вхождения $1543$ в седьмом примере. Разные слои раскрашены в разные цвета.

Примеры

№	Входные данные	Выходные данные
1	8 2 4 1543 7777 2 4 7154 8903 2 4 3451 8888 2 2 54 13 2 2 51 43 2 6 432015 512034 4 4 5431 1435 5518 7634 6 4 5432 1152 4542 2432 2302 5942	1 1 0 1 0 2 2 2

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет