| Codeforces Round 984 (Div. 3) |
|---|
| Закончено |
Однажды утром Поликарп проснулся и понял: $$$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$$$ встречается во всех слоях ковра в порядке обхода по часовой стрелке.
82 4154377772 4715489032 4345188882 254132 251432 64320155120344 454311435551876346 4543211524542243223025942
1 1 0 1 0 2 2 2
Вхождения $$$1543$$$ в седьмом примере. Разные слои раскрашены в разные цвета.
