题目描述

给定一个正整数 $N$，其中没有任何数字是 0。设 $k$ 为 $N$ 的位数。我们想通过至少擦除 0 个且至多擦除 $k-1$ 个 $N$ 的数字，并在不改变顺序的情况下连接剩余数字，从而得到 3 的倍数。确定是否可能以这种方式得到 3 的倍数。如果可能，找出必须擦除的最少数字数量以得到这样的数。

输入格式

输入$N$。

输出格式

如果不可能得到 3 的倍数，输出 -1；否则，输出必须擦除的最少数字数量以得到这样的数。

样例

35

1

369

0

6227384

1

11

-1

样例解释

【样例1说明】
通过擦除 5，我们得到数字 3，它是 3 的倍数。这里我们擦除了最少可能的数字数量是1。
【样例2说明】
注意我们可以选择不擦除任何数字。
【样例3说明】
例如，通过擦除 8，我们得到数字 622734，它是 3 的倍数。
【样例4说明】
注意我们必须至少擦除 0 个且至多擦除 $k-1$ 个数字，其中 $k$ 是 $N$ 的位数，所以我们不能擦除所有数字。
在这种情况下，不可能按照题目描述的方式得到 3 的倍数，所以我们应该输出 -1。

数据范围

$1 ≤ N < 10^{18}$, $N$ 中没有任何数字是 0。

来源

• AtCoder ABC182C