Background

Special for beginners, ^_^

Description

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

记$g(i)$为第$i$项化成二进制以后只保留最低的非零位及低位（舍弃前面的高位）后的值。

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

Format

Input

一个正整数n$(\le 10^9)$。 .

Output

一个数，表示和。

Samples

2

2

Limitation

1s, 1024KiB for each test case.