题目描述

小杨有一个正整数 $N$（不含前导零）。

他想删除 $N$ 的若干位数字（至少要保留一位），使剩下的数字按原来的顺序组成的新整数能被 $3$ 整除（允许出现前导零，例如剩下 0012 表示整数 $12$）。

请你帮小杨计算：最少需要删除多少位数字？如果无论怎样删除都不能满足要求，输出 $-1$。

输入格式

输入共一行，包含一个正整数 $N$。

输出格式

输出一个整数，表示最少需要删除的位数；若无法满足要求，输出 $-1$。

样例

35

1

123

0

2002

2

41

-1

样例解释

样例 1 中，删除数字 $5$，剩下 $3$，能被 $3$ 整除；删除 $3$ 剩下的 $5$ 不行，所以最少删 $1$ 位。

样例 2 中，$123$ 本身各位之和为 $1+2+3=6$，能被 $3$ 整除，无需删除。

样例 3 中，删除两个 $2$，剩下 00 即整数 $0$，能被 $3$ 整除；只删 $1$ 位无法满足（$002$、$202$、$200$ 各位之和分别为 $2$、$4$、$2$，均不是 $3$ 的倍数），所以最少删 $2$ 位。

样例 4 中，$41$ 删除任意一位得到 $4$ 或 $1$，都不能被 $3$ 整除；两位都删则没有数字留下，所以无解，输出 $-1$。

数据范围与约定

对于 $100\%$ 的数据，保证 $N$ 的位数不超过 $10^5$，$N$ 不含前导零（$N \geq 1$）。