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

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

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

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

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