Minimum Flips to Zero Binary String

k Teacher is analyzing a piece of virus code. The code is represented by a hexadecimal string of length at most $10^6$ (i.e. composed of digits from 0 to 9 and letters A to F). First, the hexadecimal string is converted to its binary representation (a string of 0’s and 1’s) with the most significant bit being 1 (i.e. remove any leading zeroes obtained by the standard conversion).

After obtaining the binary string, the teacher performs a series of "flip" operations. In each flip operation, you choose one bit in the binary string. If the chosen bit is in the middle of the string (i.e. not at an end), you flip the chosen bit and its immediate left and right neighbors (turning 0 to 1 and 1 to 0). If the chosen bit is at the beginning or at the end of the string, you flip the chosen bit and its only adjacent neighbor.

The task is to determine the minimum number of flip operations required to turn the binary string into a string containing only 0’s. If it is impossible, output -1.

The flipping operation can be formalized in ( \LaTeX ) as follows. Let the binary string be ( s_0,s_1,\dots,s_{n-1} ). An operation choosing index ( i ) modifies the string as:

• If ( 0 < i < n-1 ): flip ( s_{i-1}, s_i, s_{i+1} ).
  
• If ( i = 0 ): flip ( s_0 ) and ( s_1 ).
  
• If ( i = n-1 ): flip ( s_{n-2} ) and ( s_{n-1} ).
  
  The goal is to achieve ( s_0 = s_1 = \dots = s_{n-1} = 0 ) with a minimum number of operations.

inputFormat

A single line containing a hexadecimal string (with characters from 0-9 and A-F).

outputFormat

Output a single integer representing the minimum number of flip operations required to turn the binary string (obtained from the hexadecimal string) into a string of all 0’s. If it is impossible, output -1.

sample

F

2