Background

Special for beginners, ^_^

Description

菲波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

记$g(i)$为第$i$项化成二进制以后的低32位中1的个数。

给出$n$，求$\sum\limits_{i=1}^n \left[ g(i) 为奇数\right]$。

中括号是艾弗森括号，不知道的可以自行百度，以后记住。

Format

Input

一个正整数n$(\le 2 \times 10^8)$。 .

Output

一个数，表示低32位中含奇数个1的数的个数。

Samples

2

2

Limitation

1s, 1024KiB for each test case.