给定一个十进制数0≤x<2^16,将其转为二进制字符串并在高位填0补足16位, 就得到了一个长度为16的01字符串,我们用这个字符串表示4×4的棋盘, 按从左到右,从上到下的顺序将0(白子),1(黑子)放入棋盘. 例如:(447)10=(0000 0001 1011 1111)2,按顺序放入棋盘(0(白子),1(黑子)),得到如下棋盘(左) 0000 0000 0001 0000 1011 1111 1111 1111 我们现在可以交换棋盘中相邻(共享一条边的两个格子相邻 ,因此一个格子至多有4个相邻的格子)的黑,白棋子.从左图棋盘变为全部白上黑下(如右图)的棋盘, 至少需要3步. 对于给定的棋盘(保证恰有八白八黑),求将棋盘变为全部白上,全部黑下的最少交换步数.

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

输出一行一个整数,最少需要交换的步数.

样例1
447

样例2
42405

样例1
3

样例2
8

注释:
样例1
参考上图,将(2,4)处的黑子移动到(3,2)需3步.

2018江苏省小学省赛 最后一题