Маша составляет К-буквенные слова из букв П, И, Т, О, Н, причём никакие две гласные или две согласные не должны стоять рядом. Каждая буква может использоваться несколько раз или не использоваться вообще.
На вход подается натуральное число К (1 < К < 9)
Вывести все слова, которые может составить Маша, в лексикографическом порядке, каждое слово на отдельной строке. После этого вывести количество таких слов
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
ИН
ИП
ИТ
НИ
НО
ОН
ОП
ОТ
ПИ
ПО
ТИ
ТО
12
|