Рядок, що складається з літер та , називається забороненим, якщо в ньому зустрічаються три поруч літери, одна з яких , друга , а третя . Наприклад, рядок є забороненим, в той час як ні.
Обчисліть кількість незаборонених рядків довжини .
Кожний рядок містить одне число .
Для кожного значення виведіть в окремому рядку кількість незаборонених рядків довжини .