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

Вхідні дані

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

Вихідні дані

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