How Many Squares?

2000ms

65536K

Description:

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:

squares with each side parallel to a side of the matrix;
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?

Input:

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 10⁶ for any input file.

Output:

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

Sample Input:

Sample Output:

1
2

Sample Input:

1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000

Sample Output:

Informação

Provedor Codeforces

Código CF11C