Background

Special for beginners, ^_^

Description

Fib数列，大家都知道了. F[0]=1 F[1]=1 F[2]=2 F[3]=3 F[4]=5 F[5]=8 现在我们将十进制的数，转成Fib进制，对于1到7可以分成下面形式 1=1F 2=10F 3=100F 4=101F 5=1000F 6=1001F 7=1010F 8=10000F 现在我们将转化出来的1和0构成的串，连在一起，对于上面数字1到7就成了110100101100010011010... 对于这样一个无限长的字符串，问前N个字符中有多少个1

Format

Input

一个数字N，N < = 10^15

Output

前N个位置出现了多少个1

Samples

3

2

Limitation

1s, 1024KiB for each test case.