J. Number
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Consider some number without leading zeroes(but 0 is allowed). We neee to obtain new number which is divisible by three. In one move we can take any digit of this number and decrease it(if it is not 0) or increase it by 1(if it is not 9). Resulting number should not contain leading zeroes(but 0 is allowed). What is the minimum number of such moves to get a number which is divisible by three?

Input

You are given number n (0 ≤ n ≤ 1018).

Output

Output answer to the problem.

Examples
Input
12
Output
0
Input
124
Output
1
Input
0
Output
0
Input
123456788
Output
1