Заборонені рядки

Рядок, що складається з літер $A,B$ та $C$, називається забороненим, якщо в ньому зустрічаються три поруч літери, одна з яких $A$, друга $B$, а третя $C$. Наприклад, рядок $BAACAACCBAAA$ є забороненим, в той час як $AABBCCAABB$ ні.

Обчисліть кількість незаборонених рядків довжини $n$.

Вхідні дані

Кожний рядок містить одне число $n(1\le n\le 30)$.

Вихідні дані

Для кожного значення $n$ виведіть в окремому рядку кількість незаборонених рядків довжини $n$.

Приклади