Скількома способами можна замостити \(3xN\) прямокутник за допомогою \(2x1\) кісток доміно? Нижче наведено приклад замощення такими плитками прямокутника \(3x12\).

Формат вхідних даних

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

Формат вихідних даних

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

Приклад вхідних даних

2
8
12
-1

Приклад вихідних даних

3
153
2131