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.

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.

见题面 Input 部分

见题面 Output 部分

Occurrences of $1543$ in the seventh example. Different layers are colored in different colors.