给定一个十进制数0≤x≤2¹⁶,将它转化为二进制字符串并在高位填0以补足16位，就得到了一个长度为16的01字符串，我们用这个字符串表示4*4的棋盘，按从左到右，从上到下的顺序将0（白子）、1（黑子）放入棋盘。
例如，（447）₁₀=（0000 0001 1011 1111）₂，将顺序填入棋盘（0白子、1黑子）得到如下棋盘（左边棋盘）：

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

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

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

447

3