Послідовність чисел визначається наступним чином:
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).