数论

对于某个奇数i，如果他乘以2的某次方，那么i一定是这个数最大奇约数。考虑枚举2的i次方，对于一个数n，里面一共有((n>>i)+1)/2=k能整除$2^i$的数，也就是1 到1+(k-1)*2,进行等差数列求和也就是k^2累加即可

题目内容

定义$f(n)$为$n$的最大奇约数,$f(1)=1,f(2)=1,f(3)=3,f(4)=1,f(5)=5......$以此类推。

定义$g(n)=f(1)+f(2)+f(3)...+f(n)$。

请实现$g$函数。

需要确保时间复杂度尽可能低，复杂度过高的实现，可能会导致测试用例不通过。

输入描述

第一行输入一个整数$n(0<=n<=10^9)$

输出描述

输出一个整数表示答案

示例1

输入

3

输出

5

示例2

输入

4

输出

6