Викладення плитки

Скількома способами можна замостити $3\times n$ прямокутник за допомогою $2\times 1$ кісток доміно? Нижче наведено приклад замощення такими плитками прямокутника $3\times 12$.

Вхідні дані

Складаються з декількох тестів, які завершуються рядком, що містить $-1$. Кожен тест розміщено в окремому рядку і містить єдине ціле число $n(0\le n\le 30)$.

Вихідні дані

Для кожного тесту в окремому рядку виведіть кількість способів замощення.

Приклади