Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.

Дана строчка. Ее подстрокой называется некоторая непустая последовательность подряд идущих символов. Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.

Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `ab' и `ac' будет строка `abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.

Рассмотрим некоторое множество \(W\), состоящее из строк. Назовём его замыканием множество \(W\)*, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества \(W\). Таким образом, множество \(W\)* содержит пустую строку, и если строка α принадлежит множеству \(W\)*, а строка \(β\) принадлежит множеству \(W\), то строка \(αβ\) принадлежит множеству \(W\)*. Более того, все элементы множества \(W\)* можно представить в таком виде, то есть \(W\)* является пересечением всех множеств с указанными выше свойствами. Например, если \(W\)={a,ab}, то \(W\)* состоит из всех строк, в которых перед каждой буквой `b' идёт хотя бы одна буква `a'.

Задано некоторое множество строк \(W\). Требуется найти множество \(X\), такое, что \(W\)*=\(X\)* и множество \(X\) имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если \(W\)={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.

В наши дни предоставление поверхностей заборов и стен промышленных зданий рекламодателям — уже не оригинальный способ получить дополнительный заработок, а нечто само собой разумеющееся.

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером \(1\times1\times L\), на одной из сторон которого есть место для рекламы — пространство размера \(1\times L\), в которое можно вписать ровно \(L\) букв латинского алфавита.

К сожалению, иногда сделки у компании срывались, и заранее подготовленные блоки с рекламой отправлялись на склад. Со временем там скопилось приличное количество блоков различных типов (блоки разных типов отличаются друг от друга только надписью), поэтому было решено использовать их вторично.

Была предложена следующая идея: если поставить несколько блоков друг на друга и закрасить ненужные буквы, то, читая сверху вниз и слева направо, можно будет прочитать какой-нибудь другой текст, как показано на рисунке.

После того, как некоторое число \(K\) блоков, каждый из которых имеет длину \(L\), поставили друг на друга, получилась прямоугольная таблица размером \(K\times L\), в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображённом на рисунке, в результате этого процесса получилась бы строка «TOEIIZENITKN». Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока «TOEIIZENITKN».

Требуется написать программу, которая будет определять, какое минимальное количество блоков надо использовать, чтобы получить рекламную надпись, необходимую заказчику. При этом можно считать, что на складе блоков каждого типа неограниченно много.

Новый кодовый замок для владельцев нетбуков представляет головоломку не только для грабителей, но и для владельцев. На табло замка все время высвечивается некоторая комбинация нулей и единиц. Замок откроется, если на табло высветится некоторая определенная комбинация. Получить требуемую комбинацию из текущей можно нажимая в нужной последовательности кнопки, на которых написано 0 и 1 соответственно.

Если нажать кнопку с нулем, то текущая комбинация на табло сдвигается на одну позицию вправо (правая цифра при этом исчезает), а в самом левом разряде записывается 0. При нажатии на кнопку с единицей происходит то же самое, только в левый разряд записывается 1.

Известно, какая комбинация цифр сейчас находится на табло, и какую комбинацию требуется получить, чтобы открыть замок. Помогите владельцу нетбука — определите, за какое минимальное количество нажатий на кнопки можно получить требуемую комбинацию.