Gildong has a square board comprising of n lines and n sections of square cells, each comprising of a solitary digit (from 0 to 9). The cell at the j-th section of the I-th line can be addressed as (i,j), and the length of the side of every cell is 1. Gildong prefers enormous things, so for every digit d, he needs to find a triangle with the end goal that:
Correct answer will be upvoted else Multiple Downvoted. Computer science.
Gildong has a square board comprising of n lines and n sections of square cells, each comprising of a solitary digit (from 0 to 9). The cell at the j-th section of the I-th line can be addressed as (i,j), and the length of the side of every cell is 1. Gildong prefers enormous things, so for every digit d, he needs to find a triangle with the end goal that:
Every vertex of the triangle is in the focal point of a cell.
The digit of each vertex of the triangle is d.
Somewhere around one side of the triangle is corresponding to one of the sides of the board. You might expect that a side of length 0 is corresponding to the two sides of the board.
The space of the triangle is boosted.
Obviously, he can't simply be content with tracking down these triangles with no guarantees. Along these lines, for every digit d, he will change the digit of precisely one cell of the board to d, then, at that point, track down such a triangle. He transforms it back to its unique digit after he is finished with every digit. Observe the greatest space of the triangle he can make for every digit.
Note that he can put different vertices of the triangle on a similar cell, and the triangle can be a ruffian triangle; for example the space of the triangle can be 0. Additionally, note that he is permitted to change the digit of a cell from one d to another.
Input
Each test contains at least one experiments. The primary line contains the number of experiments t (1≤t≤1000).
The primary line of each experiment contains one integer n (1≤n≤2000) — the number of lines and segments of the board.
The following n lines of each experiment each contain a line of n digits without spaces. The j-th digit of the I-th line is the digit of the cell at (i,j). Every digit is one of the characters from 0 to 9.
It is ensured that the amount of n2 in all experiments doesn't surpass 4⋅106.
Output
For each experiment, print one line with 10 integers. The I-th integer is the greatest space of triangle Gildong can make when d=i−1, increased by 2.
Step by step
Solved in 4 steps with 1 images
