Kaleidoscope#5552
You are given a square board divided into n \times n unit squares, each of which is painted with some color. The integer is odd. For every k \leq n, a k \times k sub-square of this board is kaleidoscopic if:
is odd,
the vertical line going through the square's middle is its axis of symmetry (the square's left and right half are painted symmetrically),
the horizontal line going through the square's middle is also its axis of symmetry.
Compute the number of sub-squares of the board that are kaleidoscopic.
The first line contains the number of test cases . The test cases follow.
The first line of a test case contains a single integer (1 \leq n \leq 4000) - the board side length. The next lines describe the rows of the board: each of them contains a word of length over the English alphabet (only lowercase letters). The letters denote the colors of the consecutive unit squares.
For each test case, print a single integer on a separate line - the total number of kaleidoscopic sub-squares of the board.
Esempio 1