Длина S(n)

Последовательность чисел определяется следующим образом:

S(1)=1, S(2)=11, S(3)=21, S(4)=1211, S(5)=111221, S(6)=312211, ……

Необходимо вычислить длину S(n).

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

Входные данные состоят из нескольких тестов. Каждый тест содержит в отдельной строке одно целое число n (1 ≤ n ≤ 30). Последняя строка содержит n = 0 и не обрабатывается.

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

Для каждого тестового случая в отдельной строке выведите длину S(n).

Примеры