题目描述

设 $f(x)$ 表示 $x$ 在二进制表示下末尾 $0$ 的个数。

令 $F_1=F_2=1,F_n=F_{n-1}+F_{n-2}(n>2)$，求 $\sum_{i=1}^n f(F_i)$。

请注意，时间限制为 1s，空间限制为 10MB。

输入格式

一行一个整数 $x$。

输出格式

一行一个整数，表示答案。

样例

输入

19260817

输出

16050668

数据范围

对于 $25\%$ 的数据，$x\le 60$；

对于 $45\%$ 的数据，$x\le 500$；

对于 $75\%$ 的数据，$x\le 3\times 10^6$；

对于另外 $5\%$ 的数据，$x=20182018$；

对于另外 $5\%$ 的数据，$x=20192019$；

对于 $100\%$ 的数据，$1\le x\le 2147483647$。