eolymp
bolt
Try our new interface for solving problems
Problems

Kaleidoscope

Kaleidoscope

Time limit 8 seconds
Memory limit 256 MiB

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 kn, 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 data

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 (1n4000) - 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 data

For each test case, print a single integer on a separate line - the total number of kaleidoscopic sub-squares of the board.

Examples

Input example #1
1
7
bbbbbbb
abbbbbb
aabbbbb
aababbb
abbbbbb
aabaabb
aaaaaab
Output example #1
56
Source 2013 Petrozavodsk Winter Training Camp, Jagiellonian University Contest, January 25, Problem K