杜教筛·lowbit求和

题目描述

给定正整数 $n$，计算：

其中 $\text{lowbit}(x) = x \& (-x)$，表示 $x$ 的二进制表示中最低非零位所对应的值。

输入格式

一个整数 $n$（$1 \le n \le 10^{12}$）。

输出格式

输出 $S(n)$ 的值。

样例

输入

7

输出

12

说明

• $\text{lowbit}(1) = 1$
• $\text{lowbit}(2) = 2$
• $\text{lowbit}(3) = 1$
• $\text{lowbit}(4) = 4$
• $\text{lowbit}(5) = 1$
• $\text{lowbit}(6) = 2$
• $\text{lowbit}(7) = 1$

所以 $S(7) = 1+2+1+4+1+2+1 = 12$。

提示

lowbit 是积性函数。

限制

• 时间限制：1 秒
• 内存限制：256 MB