Polycarp 喜欢能被 3 整除的数字。
他有一个巨大的数字$$$s$$$。波利卡普想要从中删除可被 $$$3$$$ 整除的最大数量的数字。为此,他在相邻数字对之间进行任意数量的垂直切割。结果,经过$$$m$$$这样的削减,总共会有$$$m+1$$$个部分。 Polycarp 分析每个获得的数字并找出能被 $$$3$$$ 整除的数字。
例如,如果原始数字是$$$s=3121$$$,那么Polycarp可以通过两次切割将其切成三部分:$$$3|1|21$$$。结果,他将得到两个可以被$$$3$$$整除的数字。
Polycarp 可以进行任意数量的垂直切割,其中每次切割都在一对相邻的数字之间进行。结果数字不能包含额外的前导零(即,当且仅当该数字恰好是一个字符“0”时,该数字才能以 0 开头)。例如,007、01 和 00099 不是有效数字,但 90、0 和 10001 是有效数字。
Polycarp 最多可以获得多少个能被 $$$3$$$ 整除的数字?
输入
输入的第一行包含一个正整数 $$$s$$$。数字 $$$s$$$ 的位数在 $$$1$$$ 和 $$$2\cdot10^5$$$ 之间(含)。第一个(最左边)数字不等于 0。
输出
打印 Polycarp 通过对给定数字 $$$s$$$ 进行垂直切割可以得到的可被 $$$3$$$ 整除的最大数字数。
示例
输入 #1
3121
输出 #1
2
输入 #2
6
输出 #2
1
输入 #3
1000000000000000000000000000000000
输出 #3
33
输入#4
201920181
输出#4
4
注意
在第一个示例中,数量上的最佳切割示例集是 3|1|21。
在第二个示例中,您不需要进行任何剪切。指定的数字 6 构成一个可被 $$$3$$$ 整除的数字。
在第三个示例中,必须在每对数字之间进行剪切。结果,Polycarp 得到一位数字 1 和 $$$33$$$ 数字 0。$$$33$$$ 中的每个数字 0 形成一个能被 $$$3$$$ 整除的数字。
在第四个示例中,最佳剪辑的示例集是2|0|1|9|201|81。数字 $$$0$$$、$$$9$$$、$$$201$$$ 和 $$$81$$$ 可以被 $$$3$$$ 整除。