C - 除以3

得分：$300$ 分

问题描述

给定一个正整数 $N$，其中没有任何一位是 $0$。
设 $k$ 是 $N$ 的位数。我们希望通过从 $N$ 中擦除至少 $0$ 位、至多 $k-1$ 位数字，并将剩余的数字按原来的顺序连接起来，从而得到 $3$ 的倍数。
判断是否可能通过这种方式得到一个 $3$ 的倍数。如果可能，求出必须擦除的最小位数。

约束条件

• $1 \leq N < 10^{18}$
• $N$ 中没有任何一位是 $0$。

输入

从标准输入中按以下格式给定：

$N$

输出

如果不可能得到一个 $3$ 的倍数，则输出 -1；否则输出必须擦除的最小位数。

35

1

通过擦除数字 $5$，我们得到数字 $3$，它是 $3$ 的倍数。这里我们擦除了最小可能的位数 $1$。

369

0

请注意，我们可以选择不擦除任何位。

6227384

1

例如，通过擦除数字 $8$，我们得到数字 $622734$，它是 $3$ 的倍数。

11

-1

请注意，我们必须擦除至少 $0$ 位、至多 $k-1$ 位数字，其中 $k$ 是 $N$ 的位数，因此我们不能擦除所有位数。
在这种情况下，无法按照问题描述的方式得到一个 $3$ 的倍数，因此应该输出 -1。