Codeforces Round 984 (Div. 3) |
---|
Finished |
One morning, Polycarp woke up and realized that $$$1543$$$ is the most favorite number in his life.
The first thing that Polycarp saw that day as soon as he opened his eyes was a large wall carpet of size $$$n$$$ by $$$m$$$ cells; $$$n$$$ and $$$m$$$ are even integers. Each cell contains one of the digits from $$$0$$$ to $$$9$$$.
Polycarp became curious about how many times the number $$$1543$$$ would appear in all layers$$$^{\text{∗}}$$$ of the carpet when traversed clockwise.
$$$^{\text{∗}}$$$The first layer of a carpet of size $$$n \times m$$$ is defined as a closed strip of length $$$2 \cdot (n+m-2)$$$ and thickness of $$$1$$$ element, surrounding its outer part. Each subsequent layer is defined as the first layer of the carpet obtained by removing all previous layers from the original carpet.
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The following lines describe the test cases.
The first line of each test case contains a pair of numbers $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 10^3$$$, $$$n, m$$$ — even integers).
This is followed by $$$n$$$ lines of length $$$m$$$, consisting of digits from $$$0$$$ to $$$9$$$ — the description of the carpet.
It is guaranteed that the sum of $$$n \cdot m$$$ across all test cases does not exceed $$$10^6$$$.
For each test case, output a single number — the total number of times $$$1543$$$ appears in all layers of the carpet in the order of traversal clockwise.
82 4154377772 4715489032 4345188882 254132 251432 64320155120344 454311435551876346 4543211524542243223025942
1 1 0 1 0 2 2 2
Name |
---|