3 的倍数

题目描述

给定一个各个数位都不出现 $0$ 的正整数 $N$。

设 $N$ 的位数为 $k$。我们希望删去 $N$ 的 $0$ 个以上且不足 $k$ 个数位，并将剩余的数位按原来的顺序拼接，从而构造一个 $3$ 的倍数。

请判断能否构造出 $3$ 的倍数；如果能构造，求出构造所需的被删数位个数的最小值。

输入格式

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

$N$

输出格式

如果不能构造出 $3$ 的倍数，输出 -1；如果能构造，输出构造所需的被删数位个数的最小值。

样例

35

1

删去 $5$ 后得到的数 $3$ 是 $3$ 的倍数。此时被删数位个数为 $1$，是最小值。

369

0

请注意，也可以一个数位都不删。

6227384

1

例如，删去 $8$ 后得到的 $622734$ 是 $3$ 的倍数。

11

-1

请注意，被删数位个数必须为 $0$ 个以上且不足 $k$ 个（设 $N$ 的位数为 $k$），因此不能删去全部数位。

此时按题意无法构造出 $3$ 的倍数，所以输出 -1。

数据范围

• $1 \le N \lt 10^{18}$
• $N$ 是各个数位都不出现 $0$ 的整数