CF11C.How Many Squares?

You are given a 0-1 rectangular matrix. What is the number of squares in it? A square is a solid square frame (border) with linewidth equal to 1. A square should be at least 2 × 2. We are only interested in two types of squares:

1. squares with each side parallel to a side of the matrix;
2. squares with each side parallel to a diagonal of the matrix.

For example the following matrix contains only one square of the first type:
0000000
0111100
0100100
0100100
0111100

The following matrix contains only one square of the second type:
0000000
0010000
0101000
0010000
0000000

Regardless of type, a square must contain at least one 1 and can't touch (by side or corner) any foreign 1. Of course, the lengths of the sides of each square should be equal.

How many squares are in the given matrix?

给你一个由 0 和 1 构成的矩形矩阵。该矩阵中包含多少个“正方形”？这里的“正方形”指边宽为 1 的实心正方形框（即仅有边界，内部为空）。每个正方形的尺寸至少为 $2 \times 2$。我们仅关注以下两类正方形：

1. 每条边均与矩阵的某条边平行的正方形；
2. 每条边均与矩阵某条对角线平行的正方形。

例如，以下矩阵中仅包含一个第一类正方形：

0000000   
0111100   
0100100   
0100100   
0111100  

以下矩阵中仅包含一个第二类正方形：

0000000  
0010000  
0101000  
0010000  
0000000  

无论属于哪一类，一个正方形必须满足：

• 至少包含一个 1；
• 不能与任何“外部”的 1 相邻（包括边相邻和角相邻）；
• 每条边的长度必须相等。

给定该矩阵，其中一共有多少个正方形？

The first line contains integer t (1 ≤ t ≤ 10000), where t is the number of test cases in the input. Then test cases follow. Each case starts with a line containing integers n and m (2 ≤ n, m ≤ 250), where n is the number of rows and m is the number of columns. The following n lines contain m characters each (0 or 1).

The total number of characters in all test cases doesn't exceed 106 for any input file.

第一行包含一个整数 $t$（$1 \leq t \leq 10000$），其中 $t$ 表示输入中测试用例的数量。随后是若干测试用例。每个测试用例以一行开始，该行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 250$），其中 $n$ 表示行数，$m$ 表示列数。接下来的 $n$ 行每行包含 $m$ 个字符（每个字符为 0 或 1）。

对于任意输入文件，所有测试用例中的字符总数不超过 $10^6$。

You should output exactly t lines, with the answer to the i-th test case on the i-th line.

你应该输出恰好 $t$ 行，其中第 $i$ 行为第 $i$ 个测试用例的答案。