Length of S(n)

A number sequence is defined as following:

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

Now, we need you to calculate the length of S(n).

Input

The input consists of multiple test cases. Each test case contains one integers n (1 ≤ n ≤ 30). n = 0 signal the end of input.

Output

Length of S(n).

Examples