一天早上,Polycarp 醒来,意识到 $$$1543$$$ 是他一生中最喜欢的数字。
波利卡普那天一睁开眼睛,首先看到的就是一块大小为 $$$n$$$ 的大墙毯,由 $$$m$$$ 个细胞组成; $$$n$$$ 和 $$$m$$$ 是偶数整数。每个单元格包含从 $$$0$$$ 到 $$$9$$$ 的数字之一。
Polycarp 很好奇,顺时针遍历时,数字 $$$1543$$$ 在地毯的所有层$$$^{\text{*}}$$$ 中会出现多少次。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。以下几行描述了测试用例。
每个测试用例的第一行包含一对数字 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n, m \leq 10^3$$$, $$$n, m$$$ - 偶数整数)。
接下来是 $$$n$$$ 行,长度为 $$$m$$$,由从 $$$0$$$ 到 $$$9$$$ 的数字组成 - 地毯的描述。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出一个数字——$$$1543$$$按照顺时针遍历的顺序出现在地毯所有层中的总次数。
示例
输入 #1
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 1 0 1 0 2 2 2
注意
在第七个示例中出现 $$$1543$$$。不同的层有不同的颜色。