Description
Dio, an evil vampire, does all kinds of evil and nobody can fight against him.
However, there's a brave man, JoJo, standing out and using all his ability to defeat him.
Everyone appreciate JoJo's great achievement and the world becomes safe and peace again.
Unfortunately, since Dio is a vampire, he revives himself again and tries to make more chaos......
We have known that there is a star-shaped birthmark on Dio's neck. To make sure that Dio is not able to enter our country, in the airport, we will use a special technique to scan a part of the visitors' skin and transfer the raw image to gray scale (0-255, 0 means black and 255 means white).
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the following condition will be satisfied:
(1) A[X][j]=255, for all 0<=j<N (The values in the Xth row are all 255)
(2) A[i][Y]=255, for all 0<=i<N (The values in the Yth column are all 255)
(3)
A[X+i][Y+i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N
A[X+i][Y-i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N
(The values of two diagonals from the centers are all 255)
For example, a star looks like:
In this problem, given T square matrices wth size N, you are asked to find out how many stars in each matrix respectively.
Hint.
If you cannot pass all the testcases, you can try to use extra arrays to record some infomation when you read the input data.
By doing so, you can immediately determine whether a point is a star.
Input
There are three parts of the input:
(1) The number of testcases, T. 1<=T<=1000
(2) The size of the square matrices, N. 1<=N<=2048
(3) T N*N matrices separated by a newline character. 0<=The values in the matrices<=255.
Output
The number of stars in each matrix.
Note that you need to print "\n" in the end of each answer.