Description

Teacher k is studying the code of a virus program. This code is information consisting of a hexadecimal string of length at most $10^6$ (that is, characters 0 to 9 and A to F). Now teacher k wants to convert it into a binary $0/1$ string (and at this time, you must ensure that the highest bit is $1$). Then, perform a “flip” operation on this $0/1$ string.

For each “flip” operation, teacher k can choose one position in the $0/1$ string, and flip this bit and its two adjacent bits (three bits in total) separately (that is, $0$ becomes $1$, and $1$ becomes $0$). If the chosen position is at the beginning or the end of the sequence, then flip this bit and the existing adjacent bit(s).

Teacher k wants to know how to use the minimum number of “flip” steps to turn this $0/1$ string into an all-$0$ string.

Input Format

A hexadecimal string consisting of 0 to 9 and A to F.

Output Format

Output the minimum number of “flip” steps needed to turn it into an all-$0$ string. If it is impossible to turn it into an all-$0$ string no matter what, output No.

15

3

FF

3

10

No

Hint

Explanation of the samples:

Hexadecimal 15 corresponds to binary 10101. By flipping positions $1/3/5$, it can all become $0$.

Hexadecimal FF corresponds to binary 11111111. By flipping positions $2/5/8$, it can all become $0$.

Hexadecimal 10 corresponds to binary 10000, and it cannot be turned into all $0$.

Translated by ChatGPT 5