Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `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}.

Петя и его друг Андрейка только что познакомились с китайской мифологией. Особенно им понравились драконы. Поэтому мальчики решили сделать своих драконов из проволоки. Андрейка взял белую проволоку и согнул из неё дракона Лун-Инь: этот дракон спал, свернувшись клубком на столе. Тогда Петя взял чёрную проволоку и согнул дракона Лун-Ян. Этот дракон ничем не походил на Андрейкиного Лун-Иня. Его тело состояло из отрезков прямых, а когда он спал, то сворачивался в виде плоской замкнутой несамопересекающейся ломаной. Более того, Лун-Ян не ложился плашмя на стол для сна, а вставал перпендикулярно поверхности. Удержать равновесие дракон может только тогда, когда существуют две его различные точки, касающиеся стола, такие что центр масс дракона находится строго между ними.

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