Система телефонных номеров в России устроена следующим образом. Все телефонные номера имеют одну и ту же длину — M цифр. Номер состоит из двух частей: несколько первых цифр номера составляют код города, остальные цифры определяют номер абонента в пределах этого города.

В процессе развития сети коды городов регулярно меняются, при этом, коды различных городов обязательно различны. В остальном коды могут быть совершенно произвольными, в том числе код одного города может быть началом кода другого (например, код Нижнего Новгорода — 831, а код Сарова — 83130) и т. п. Если коды нескольких городов являются началом M-значного номера абонента, кодом города этого номера считается наидлиннейший из таких кодов. Так, если есть всего четыре города: Нижний Новгород, Балахна, Дзержинск и Саров с кодами, соответственно, 831, 83144, 8313 и 83130, и M = 9, то: телефоны 831123456 и 831412345 — телефоны Нижнего Новгорода, 831312345 — телефон Дзержинска, 831301234 — Сарова, а 831441234 — Балахны.

В этой задаче мы не будем учитывать различные другие ограничения на телефонные номера, существующие в реальности (например, в реальности никакой номер абонента в городе не может начинаться на 03, т. к. 03 — это телефон скорой помощи). Мы будем считать, что любой из 10^M возможных M-значных номеров является допустимым телефонным номером.

Нетривиальной задачей становится задача определения, сколько всего телефонных номеров может быть выдано в каждом городе. Например, в приведённом выше примере в Балахне и Сарове могут быть выданы 10 000 телефонных номеров (все четырёхзначные номера), в Дзержинске могут быть выданы 90000 телефонных номеров — все пятизначные телефонные номера, кроме начинающихся на ноль, а в Нижнем Новгороде могут быть выданы 890 000 номеров — все шестизначные номера, кроме тех, которые начинаются на цифру 3, а также на последовательность 44.

Напишите программу, которая решит эту задачу для произвольного набора кодов городов.

Цепочкой слов длины n назовем последовательность слов w₁, w₂, ..., w_n такую, что для 1 ≤ i ≤ n слово w_i является собственным префиксом слова w_i + 1.

Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.

Задано множество слов S = {s₁, s₂, ..., s_m}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.

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

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

Для того, чтобы придать забору более спокойный и гармоничный вид, он несколько раз производит следующую операцию: выбирает некоторый цвет и отрезок, после чего перекрашивает этот отрезок забора в выбранный цвет. По своей творческой натуре, Смолокуров может в корне менять концепцию узора по нескольку раз за час, поэтому иногда он перекрашивает одну и ту же планку несколько раз. Кроме того, Витезслав не хочет, чтобы какой-то узор повторялся слишком часто. Для того, чтобы избежать этого, он иногда проверяет, не совпадает ли один отрезок забора с другим.

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