dottle is a robot.

One day, dottle sees a decimal integer $n$ on the blackboard, and it is guaranteed that the decimal representation of $n$ does not contain any $0$.

dottle believes that multiples of $3$ are "good," so he wants to erase some digits from $n$ to make it a good number.

The process of erasing a digit can be viewed as deleting one digit from the decimal representation of $n$ and concatenating the remaining parts in order. For example, if the third digit from the left of $114514$ is erased, it becomes $11514$.

Note that an empty blackboard is not allowed. That is, if the decimal representation of $n$ has $k$ digits, the number of deletion operations performed cannot exceed $k-1$.

dottle wants to know the minimum number of digits he needs to erase to make $n$ a good number, or to be told that there is no solution.

Input

A single positive integer $n$.

Output

If a solution exists, output a single integer representing the answer.

Otherwise, output dottle bot.

Examples

Input 1

114514

Output 1

1

Note 1

Deleting the $4$ at the third position from the left results in $11514$, which is a multiple of $3$.

Input 2

369

Output 2

0

Note 2

$369$ is a multiple of $3$.

Input 3

11

Output 3

dottle bot

Note 3

Note that it is not allowed to erase all digits, so there is no solution.

Input 4

283959283666555555

Output 4

2

Constraints

There are $10$ test cases in total, each worth $10$ points. For all test cases, it is guaranteed that $1\leq n\leq 10^{18}$ and the decimal representation of $n$ does not contain $0$.

The specific constraints are as follows: