给定一个十进制数0<=x<2^16,将它转换为二进制字符串并在高位填0以补足16位，就得到了一个长度为16的01字符串，我们用这个字符串表示4*4的棋盘，按从左到右、从上到下的顺序将0（白子）、1（黑子）放入棋盘。 例如： (447)10=(0000 0001 1011 1111)2, 按顺序填入棋盘（0白子、1黑子），得到如下棋盘（左边棋盘）： [IMG]http://jsoi.jzhx.net/web/web/wwwroot/wxdfiles/2409.png[/IMG] [IMG]http://192.168.21.227/web/web/wwwroot/wxdfiles/2409.png[/IMG] 我们可以交换棋盘中相邻（共享一条边的两个格子相邻，因此一个格子至多有4个相邻的格子）的黑色和白色棋子。从左图的棋盘变为全部白子在上、全部黑子在下（右边棋盘所示）的棋盘，至少需要3步。 对于给定的棋盘（保证棋盘中恰好有8个白子和8个黑子），求把棋盘变为全部白子在上，全部黑子在下最少的交换步数。

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

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

(1)
447

(2)
42405

(1)
3
参考上图，将（2，4）处的黑子移动到（3，2）需要3步

（2）
8

（42405）10=（1010 0101 1010 0101）2 见上面的图