题目描述

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

例如，$(447)_{10} = (0000 0001 1011 1111)_2$，按顺序填入棋盘（$0$ 白子、$1$ 黑子），得到如下棋盘（左边棋盘）：

我们现在可以交换棋盘中相邻（共享一条边的两个格子相邻，因此一个格子至多有 $4$ 个相邻的格子）的黑色和白色棋子。从左图的棋盘变为全部白子在上、全部黑子在下（右边棋盘所示）的棋盘，至少需要 $3$ 步。

对于给定的棋盘（保证棋盘中恰好有 $8$ 个白子和 $8$ 个黑子），求把棋盘变为全部白子在上、全部黑子在下最少的交换步数。

输入格式

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

输出格式

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

447

3

42405

8

提示

样例解释

样例 $1$

参考上图，将 $(2, 4)$ 处的⿊⼦移动到 $(3, 2)$ 需要 $3$ 步。

样例 $2$

如下图所示，$(42405)_{10} =(1010 0101 1010 0101)_2$。

数据规模

$50\%$ 的测试数据满足棋盘可以在 $6$ 次交换内变为白子在上、黑子在下。

所有数据保证 $0 ≤ x < 2^{16}$，且 $x$ 转换为二进制后恰好有 $8$ 个 $1$。

本题原始满分为 $20\text{pts}$。