На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как c_i, то оно будет считаться по формуле c_i = c_i - 1 + c_i - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.

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

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

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

Вам дана структура министерства. Каждый работник имеет одного начальника и не более трёх подчинённых(возможно ноль). Единственным исключением является министр  — у него нет начальника(но так же не более трех подчинённых). Конечно нет определённого порядка, в котором перечисляются подчинённые. Департамент состоит из должностного лица, всех его подчинённых и их подчинённых, и т.д.

Есть два особых случая:

• Департамент, в котором должностное лицо  — сам министр, тогда этот департамент есть всё министерство.

• Департамент, в котором у должностного лица нет ни одного подчинённого.

Высотой департамента назовем длину максимальной последовательность сотрудников x ₁ , ..., x _d такую, что сотрудник x _i является начальником сотрудника x _{i + 1} для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .

Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x _A из департамента A сотрудника x _B из департамента B , таким образом, что сотрудник x _A является начальником сотрудником y _A , тогда и только тогда, когда x _B является начальником y _B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.

На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .

Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n ₁ , ..., n _d , где d это высота всего министерства, а n _i — количество различных департаментов высоты i .

Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.

У одного медведя есть N строк (обозначим i -ю из них x _i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x _i и x _j ( i < j ) могут принадлежать одной такой последовательности, если x _i является и префиксом, и суффиксом x _j .

Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.

У маленького Матежа возникла проблема с решением следующей задачи.

У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.

Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.