Вам задана прямоугольная матрица, состоящая из нулей и единиц. Ваша задача посчитать число квадратов в ней. В данном случае квадратом называется рамка (бордюр) ширины 1 квадратной формы. Минимальный размер квадрата 2 × 2. Существует два типа квадратов:
- каждая сторона которых параллельна стороне заданной матрицы;
- каждая сторона которых параллельна одной из диагоналей заданной матрицы.
Этот пример содержит единственный квадрат первого типа:
0000000
0111100
0100100
0100100
0111100
А этот — квадрат второго типа:
0000000
0010000
0101000
0010000
0000000
Независимо от типа квадраты не могут касаться лишних единиц (как по стороне так и по углу). Конечно, длины сторон для любого квадрата равны между собой.
Напишите программу, которая выводит количество квадратов на заданной матрице.
Выходные данные
Выведите t строк, i-ая строка должны содержать ответ для i-го набора входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000
|
1
2
|
|
2
|
1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000
|
3
|