POLSKI SPOJ

Prostokątem-palindromem jest prostokąt wypełniony literami spełniający jedną własność: wszystkie kolumny oraz wszystkie wiersze tego prostokąta są palindromami.

Masz dany kwadrat N x N wypełniony literami. Znajdź w nim wszystkie prostokąty-palindromy o nieparzystej szerokości i nieparzystej wysokości oraz wypisz ich liczbę.

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych T (1 ≤ T ≤ 1000).

Pierwsza linia każdego zestawu danych zawiera jedną liczbę N (1 ≤ N ≤ 500).

Każda z następnych N linii zawiera N małych liter z alfabetu łacińskiego.

Ponadto każdy plik testowy spełnia jeden z trzech warunków:

• T ≤ 1000 && N ≤ 50
• T ≤ 100 && N ≤ 200
• T ≤ 10 && N ≤ 500
  

Wyjście

Dla każdego zestawu danych należy wypisać liczbę prostokątów-palindromów o nieparzystej szerokości i nieparzystej wysokości znajdujących się w danym kwadracie.

Przykład

Wejście:
2
3
abc
aaa
abc
10
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

Wyjście:
13
900