Однажды утром Поликарп проснулся и понял: \(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\) встречается во всех слоях ковра в порядке обхода по часовой стрелке.
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач