eolymp
bolt
Try our new interface for solving problems
Məsələlər

Калейдоскоп

Калейдоскоп

Zaman məhdudiyyəti 8 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

  • k нечетно,

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

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

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

Giriş verilənləri

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
1
7
bbbbbbb
abbbbbb
aabbbbb
aababbb
abbbbbb
aabaabb
aaaaaab
Çıxış verilənləri #1
56
Mənbə 2013 Petrozavodsk Winter Training Camp, Jagiellonian University Contest, Январь 25, Задача K