← 返回题目列表

Codeforces · 2036/D

D. 我爱1543

中文机器翻译题面 查看原题

一天早上,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$$$。不同的层有不同的颜色。