Kaleidoscope
You are given a square board divided into n x n unit squares, each of which is painted with some color. The integer n is odd. For every k ≤ n, a k x k sub-square of this board is kaleidoscopic if:
k 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 though the square's middle is also its axis of symmetry.
Compute the number of sub-squares of the board that are kaleidoscopic.
Input
The first line contains the number of test cases t. The test cases follow.
The first line of a test case contains a single integer n (1 ≤ n ≤ 4000) - the board side length. The next n lines describe the rows of the board: each of them contains a word of length n over the English alphabet (only lowercase letters). The letters denote the colors of the consecutive unit squares.
Output
For each test case, print a single integer on a separate line - the total number of kaleidoscopic sub-squares of the board.