问题描述

给定一个正整数 $n$ , 找出所有 $n$ 的倍数的二进制表示中最少有多少个 1 。

输入格式

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

输出一行包含一个整数表示答安。

14 是 7 的倍数, 其二进制表示为 1110 , 有 3 个 1 。也是 7 的倍数, 二进制表示中也有 3 个 1 。可以证明 7 的其他倍数的二进制表示不会具有更少的 1 。

对于 10% 的评测用例, $n \leq 10$ :

对于 25% 的评测用例, $n \leq 200$ :

对于 50% 的评测用例, $n \leq 5000$ :

对于所有评测用例, $1 \leq n \leq 10^6$ 。