C. How Many Squares?
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

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:00000000010000010100000100000000000

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 106 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.

Examples
Input
28 8000100010010100001000100100000100100010000101000110100111100001110 101111111000100000100010110010001011001010100000110110010010101010101000100100100010000010001111111000
Output
12
Input
112 11111111111111000000000110111111101101000001011010110010110101100101101000001011010000010110111111101100000000011111111111100000000000
Output
3