题目描述

小 $A$ 最近迷上了二进制，他发现二进制有很多神奇的性质。今天他想研究一下二进制中 $1$ 的个数的问题。

给定一个正整数 $N$，请输出 $1 \sim N$ 的所有正整数的二进制表示中 $1$ 的个数之和。

例如，$N = 5$ 时：

• $1$ 的二进制是 1，有 $1$ 个 $1$
• $2$ 的二进制是 10，有 $1$ 个 $1$
• $3$ 的二进制是 11，有 $2$ 个 $1$
• $4$ 的二进制是 100，有 $1$ 个 $1$
• $5$ 的二进制是 101，有 $2$ 个 $1$

所以答案是 $1 + 1 + 2 + 1 + 2 = 7$。

输入格式

输入一个正整数 $N$。

输出格式

输出一个整数，表示 $1 \sim N$ 的所有正整数的二进制表示中 $1$ 的个数之和。

样例

输入

5

输出

7

数据范围

对于 $30\%$ 的数据，满足 $1 \le N \le 100$。

对于 $60\%$ 的数据，满足 $1 \le N \le 10^6$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^{15}$。