Chessboard Swap

Given a decimal number \(x\), convert it to a 16-bit binary string (with leading zeros if necessary). Interpret this binary string as a 4×4 chessboard filled in row‐major order (from left to right and top to bottom), where each character denotes a piece: \(0\) for a white piece and \(1\) for a black piece.

You are allowed to swap two adjacent pieces (two cells sharing a common edge). The goal is to transform the board into a configuration where all white pieces are on the top half (first two rows) and all black pieces are on the bottom half (last two rows). In other words, in the final chessboard the first 8 cells in row‐major order should be \(0\) (white) and the last 8 cells should be \(1\) (black).

It is guaranteed that the board contains exactly 8 white pieces and 8 black pieces. Compute the minimum number of swaps required to reach the goal configuration.

For example, consider \(x = 447\): \[ 447_{10} = 0000\;0001\;1011\;1111_{2} \] Filling the board in order gives the configuration shown on the left. By a series of adjacent swaps, one can achieve the configuration with all white pieces on top and all black pieces on bottom (as shown on the right) in at least 3 steps.

inputFormat

The input consists of a single line containing a decimal integer \(x\) (0 \(\leq x < 2^{16}\)). The 16-bit binary representation of \(x\) will have exactly 8 ones and 8 zeros.

Note: The binary string is obtained by converting \(x\) into binary and adding leading zeros so that its length is 16.

outputFormat

Output a single integer: the minimum number of adjacent swaps needed to transform the given chessboard into a configuration where the top half (first two rows) consists only of white pieces (\(0\)) and the bottom half (last two rows) only of black pieces (\(1\)).

sample

447

3