题目背景

翻译自 CSES-1146 题。

题目描述

你的任务是计算从 $1$ 到 $n$ 之间的所有整数的二进制表示中 $1$ 的个数。

输入格式

输入的唯一一行包含一个整数 $n$。

输出格式

输出从 $1$ 到 $n$ 之间所有整数的二进制表示中 $1$ 的个数。

样例

输入

7

输出

12

样例1解释

从 1 到 7 的整数的二进制表示分别是：
1 = 1

2 = 10

3 = 11

4 = 100

5 = 101

6 = 110

7 = 111

这些二进制表示中共有 12 个 1，因此输出 12。

说明/提示

$1 \leq n \leq 10^{15}$。