Problem Description

Teacher k is studying the code of a virus program. The code consists of a hexadecimal string of length no more than $10^6$, composed of characters from 0 to 9 and A to F. Teacher k needs to convert this string into a binary 0/1 sequence (ensuring the highest bit is 1) and then perform a "flip" operation on this 0/1 sequence.

For each "flip" operation, Teacher k can choose any one bit in the 0/1 sequence and flip this bit along with its two adjacent bits, totaling three bits (i.e., 0 becomes 1, and 1 becomes 0). If the chosen bit is at the beginning or end of the sequence, only flip this bit and its adjacent bit(s) that exist.

Teacher k wants to know the minimum number of "flip" operations required to turn this 0/1 sequence into a sequence of all 0s.

Input Format

A hexadecimal string composed of characters from 0 to 9 and A to F.

Output Format

The minimum number of "flip" operations needed to turn the sequence into all 0s. If it is impossible to turn the sequence into all 0s, output No.

Sample Input and Output

Sample Input #1

15

Sample Output #1

3

Sample Input #2

FF

Sample Output #2

3

Sample Input #3

10

Sample Output #3

No

Notes

Explanation of Samples:

The hexadecimal 15 corresponds to the binary 10101. Flipping the 1st, 3rd, and 5th bits can turn it into all 0s.

The hexadecimal FF corresponds to the binary 11111111. Flipping the 2nd, 5th, and 8th bits can turn it into all 0s.

The hexadecimal 10 corresponds to the binary 10000. It is impossible to turn it into all 0s.

见题面 Input 部分

见题面 Output 部分