YiYi is a smart boy, he is fascinated in solving eccentric problems. One day when he was reading a book, he came across a very interesting problem. After a few time’s thinking, he finally get the solution. YiYi considers this solution very heuristic, now he decides to show this problem to you so that you can also enjoy the happiness of solving this interesting problem. Here is the description of the problem:

Suppose at first you have a sequence, S_{1}, consists of two numbers: 1, 1. According to some rule you can get the sequence S_{n} from the sequence S_{n-1}.Once you get S_{n-1}, you will be asked to insert one n between a and b if a and b are two adjacent numbers in S_{n-1} and a + b = n. After you have inserted all possible n you finally get S_{n}. You can also get the sequence S_{n+1} using the same method and so on.

For example,S_{1} = 1,1.Since 1 + 1 = 2, we will insert 2 between two 1s and then we get S_{2}, S_{2} = 1,2,1. Now we will insert two 3s in the sequence to get S_{3}, as you can see, S_{3} = 1,3,2,3,1. In the same way, we know S_{4} = 1,4,3,2,3,4,1, S5 = 1,5,4,3,5,2,5,3,4,5,1 and so on.

Here the question comes: give you n, you will be asked to output the number of n in S_{n}. For example if n = 5, you will output 4 since there are 4 5s in S_{5}.