该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

一天早晨，Polycarp 醒来后意识到 1543 是他一生中最喜欢的数字。

那天他睁开眼睛看到的第一件事，就是一块大小为 n×m 的大地毯，其中 n 和 m 都是偶数。每个格子里都包含一个 0 到 9 的数字。

Polycarp 很好奇，在顺时针遍历地毯的所有“层”时，数字 1543 会出现多少次。

“层”∗ 的定义如下：对于一个 n×m 的地毯，第一层是指包围地毯外部的、厚度为 1 的闭合带，其长度为 2⋅**(n+m−2)**。每一层之后的层，都是在去掉所有之前的层后，对剩下的地毯取第一层

Format

Input

输入的第一行为一个整数 t（1≤t≤100），表示测试用例的数量。接下来的每组测试用例描述如下：

每组测试用例的第一行为两个整数 n 和 m（2≤n,m≤1e3，n,m 为偶数）。

接下来有 n 行，每行包含 m 个数字字符（0 到 9），描述地毯的内容。

保证所有测试用例中 n⋅m 的总和不超过 1e6。

Output

对于每个测试用例，输出一个整数，表示在顺时针遍历所有层时，数字 1543 出现的总次数。

Samples

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

Limitation

1s, 1024KiB for each test case. 图中展示了第七个样例中 1543 的出现位置。不同的层用不同颜色标记。