题目描述

我们已经知道 2 进制到 10 进制表示方法，与16 进制类似，我们考虑 11~36 进制，即用$a$代表 10，$b$代表 11等。

我们想知道给定一个 10 进制数$n$，其在2~36 进制下的所有进制表示中，含有1的数量最多是多少。

比如 4在二进制下表示为$(100)_2$，只有一个1。

输入描述

在一行上输入一个整数$n(1\le n\le 3\times 10^5)$代表给定的十进制数。

输出描述

在一行上输出一个整数表示答案。

样例

输入

4

输出

2

样例解释

3进制下1的个数最多，$4=(11)_3$，因此最多1的个数为2。