You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC182C] To 3

题面翻译

给定正整数 $n$ ，保证 $n$ 的每一位都不是 $0$ ，求最少把 $n$ 去掉多少位后能使得剩下的数是 $3$ 的倍数。如果无法做到这一点，输出 $-1$ 。如果原数已经是 $3$ 的倍数，输出 $0$ 即可。

题目描述

各桁に $0$ が出現しないような正の整数 $N$ が与えられます。 $N$ の桁数を $k$ とします。$N$ の桁を $0$ 個以上 $k$ 個未満消して、残った桁をそのままの順序で結合することで $3$ の倍数を作りたいです。 $3$ の倍数を作ることができるか判定し、作ることができるなら作るのに必要な最少の消す桁数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$

输出格式

$3$ の倍数を作ることができないなら -1 を、作ることができるなら作るのに必要な最少の消す桁数を出力せよ。

样例 #1

样例输入 #1

35

样例输出 #1

1

样例 #2

样例输入 #2

369

样例输出 #2

0

样例 #3

样例输入 #3

6227384

样例输出 #3

1

样例 #4

样例输入 #4

11

样例输出 #4

-1

提示

制約

• $1\ \le\ N\ \lt\ 10^{18}$
• $N$ は各桁に $0$ が出現しない整数

Sample Explanation 1

$5$ を消した $3$ という数は $3$ の倍数です。このとき消した桁数は $1$ で最少です。

Sample Explanation 2

$1$ つも桁を消さなくてもいいことに注意してください。

Sample Explanation 3

例えば、 $8$ を消した $622734$ は $3$ の倍数です。

Sample Explanation 4

消す桁数は $N$ の桁数を $k$ として $0$ 個以上 $k$ 個未満でなければならないため、全部の桁を消すことはできないことに注意してください。 この場合問題文に従って $3$ の倍数を作ることは不可能なため -1 を出力します。