Укладка плиток

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

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

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

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

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

Примеры