题目描述

给定一个正整数 $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\ \le\ N\ \lt\ 10^{18}$
• $N$ 中没有任何数字是 $0$ 。