Квадратная доска разделена на n x n единичных квадратов, каждый из которых покрашен определенным цветом. Значение n нечетно. Для каждого k ≤ n, подквадрат k x k является калейдоскопом, если:

• k нечетно,
• вертикальная линия, проходящая через центр подквадрата, является осью симметрии (левая и правая часть квадрата покрашены одинаково),
• горизонтальная линия, проходящая через центр подквадрата, также является осью симметрии.

Вычислите количество подквадратов на доске, которые являются калейдоскопами.

Входные данные

Первая строка содержит количество тестов t. Далее идут сами тесты.

Первая строка каждого теста содержит длину n (1 ≤ n ≤ 4000) стороны доски. Следующие n строк описывают строки доски: каждая из них содержит слово из n букв английского алфавита (только нижнего регистра). Буквы указывают на цвет единичных квадратов.

Выходные данные

Для каждого теста вывести в отдельной строке общее количество подквадратов доски, являющимися калейдоскопом.