409190: GYM103451 J Number

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Numbertime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
12
Output
0
Input
124
Output
1
Input
0
Output
0
Input
123456788
Output
1

加入题单

上一题 下一题 算法标签: