配点 : $300$ 点

問題文

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

制約

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

入力

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

$N$

出力

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

35

1

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

369

0

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

6227384

1

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

11

-1

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