Description

给你一个数字矩阵，第 $i$ 层为长度为 $n - i + 1$ 或者 $m - i + 1$的边，问当顺时针遍历每一层的时候，$1234$ 会出现多少次

Format

Input

第一行输入一个 $t$ 表示测试用例数量

对于每个测试：

第一行输入两个数字 $n$ 和 $m$ 表示矩阵大小

接下来 $n$ 行每行 $m$ 个数 $a_{i,j}$ 表示矩阵 $a$

保证 $t$ 组测试 $n * m$ 之和不超过 $10^6$

Output

输出一个数字，表示1234按顺时针遍历出现在矩阵的所有层中的总次数

Samples

1
4 4
1234
0120
0430
0000

2

Limitation

$1 \leq t \leq 100$

$2 \leq n,m \leq 10 ^ 3$，保证$n,m$都是偶数

$0 \leq a_{i,j} \leq 9$