给定一个十进制数0 ≤ x < 2¹⁶，将它转换为二进制字符串并在高位填 0 以补足 16 位，就得到了一个长度为 16 的 01 字符串，我们用这个字符串表示 4 × 4的棋盘，按从左到右、从上到下的顺序将 0 (白子)、1 (黑子)放入棋盘。

我们现在可以交换棋盘中相邻(共享一条边的两个格子相邻，因此一个格子至多有 4 个相邻的格子)的黑色和白色棋子。从左图的棋盘变为全部白子在上、全部黑子在下(右边棋盘所示)的棋盘，至少需要 3 步。
对于给定的棋盘(保证棋盘中恰好有 8 个白子和 8 个黑子)，求把棋盘变为全部白子在上、全部黑子在下最少的交换步数。

输入一行一个整数x，为十进制表示下的棋盘。

输出一行一个整数，最少需要交换的步数。

447

3

42405

8