P409190 - GYM103451 J Number - SSOJ - 省实信息奥赛评测系统

Memory Limit：64 MB Time Limit：2 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

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 ≤ 10¹⁸).

Output

Output answer to the problem.

ExamplesInput

Output

Input

Output

Input

Output

Input

123456788

Output

Krosh Kaliningrad Contest 2

409190: GYM103451 J Number

Description

Source/Category

加入题单