题目描述

给出一个正整数 $n$，按如下规则构造新数，最终求构造完成后新数的长度：

1. 在 $n$ 的右边加入 $n$ 取整数的一半，形成新数；
2. 接着在新数的右边加入上一次加入的数取整数的一半；
3. 重复上述操作，直到要加入的数为 $0$ 时，停止加数。

例如 $n=37$ 时，构造过程为：

• $37$ 的一半为 $18$（取整数），加到右边得到 $3718$；
• $18$ 的一半为 $9$，加到右边得到 $37189$；
• $9$ 的一半为 $4$，加到右边得到 $371894$；
• $4$ 的一半为 $2$，加到右边得到 $3718942$；
• $2$ 的一半为 $1$，加到右边得到 $37189421$；
• $1$ 的一半为 $0$，加数结束，最终新数是 $8$ 位。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示加数结束后新数的长度。

样例

37

8

数据范围

• $1 \le n \le 100000$