C. Сколько квадратов?
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана прямоугольная матрица, состоящая из нулей и единиц. Ваша задача посчитать число квадратов в ней. В данном случае квадратом называется рамка (бордюр) ширины 1 квадратной формы. Минимальный размер квадрата 2 × 2. Существует два типа квадратов:

  1. каждая сторона которых параллельна стороне заданной матрицы;
  2. каждая сторона которых параллельна одной из диагоналей заданной матрицы. 

Этот пример содержит единственный квадрат первого типа: 
0000000 
0111100 
0100100 
0100100 
0111100

А этот — квадрат второго типа:
0000000
0010000
0101000
0010000
0000000

Независимо от типа квадраты не могут касаться лишних единиц (как по стороне так и по углу). Конечно, длины сторон для любого квадрата равны между собой.

Напишите программу, которая выводит количество квадратов на заданной матрице.

Входные данные

Первая строка содержит целое число t (1 ≤ t ≤ 10000), где t это количество наборов входных данных в тесте. Далее следуют сами наборы. Каждый набор начинается строкой, состоящей из двух целых чисел n and m (2 ≤ n, m ≤ 250), где n это количество строк, а m — количество столбцов заданной матрицы. Следующие n строк содержат по m символов каждая: (символы 0 или 1).

Суммарное количество элементов во всех матрицах для одного теста не превосходит 106.

Выходные данные

Выведите t строк, i-ая строка должны содержать ответ для i-го набора входных данных.

Примеры
Входные данные
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
Входные данные
1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000
Выходные данные
3