#描述#
Let's consider an infinite sequence A(i) defined as follows:
(1) A(i) = 1, for all i<=1;
(2) A(i) = A([(i+1)/2]) + A([(i-1)/2]), for all i > 1, where [x] denotes the floor function of x. floor(x) is the max integer that not bigger then x;
You will be given n. Calculate A(n)(index is 0-based).

#格式#
##输入格式##
Each line will contain one integers n (0&lt=n&lt=10^9). Process to end of file.

##输出格式##
For each n, output the n-th element in one line.

#样例1#
##样例输入1##

0
3
5

##样例输出1##

1
3
5

#限制#
1000ms
32768KB

#提示#

#来源#
laddiexu