Запрещенные строки

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

Вычислите количество незапрещенных строк длины $n$.

Входные данные

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

Выходные данные

Для каждого значения $n$ выведите в отдельной строке количество незапрещенных строк длины $n$.

Примеры