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.

Input

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$$$.

Output

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.

Note

$\text{[math]}$ Occurrences of $$$1543$$$ in the seventh example. Different layers are colored in different colors.

I Love 1543

Examples