CF1005D.Polycarp and Div 3

Polycarp likes numbers that are divisible by 3.

He has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$.

For example, if the original number is $s=3121$, then Polycarp can cut it into three parts with two cuts: $3|1|21$. As a result, he will get two numbers that are divisible by $3$.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by $3$ that Polycarp can obtain?

Polycarp 喜欢能被 3 整除的数字。

他有一个非常大的数字 $s$。Polycarp 想从中切出尽可能多的能被 3 整除的数字。为此，他可以在任意一对相邻数字之间进行任意次数的竖直切割。经过 $m$ 次这样的切割后，总共会得到 $m+1$ 个部分。Polycarp 分析每个得到的数字，并统计其中能被 3 整除的数字的个数。

例如，若原始数字为 $s=3121$，则 Polycarp 可以用两次切割将其分为三部分：$3|1|21$。结果，他将得到两个能被 3 整除的数字。

Polycarp 可以进行任意次数的竖直切割，每次切割均位于一对相邻数字之间。所得数字不能包含多余的前导零（即：一个数字可以以 0 开头，当且仅当该数字恰好为单个字符 '0'）。例如，007、01 和 00099 是无效数字，而 90、0 和 10001 是有效数字。

Polycarp 最多能得到多少个能被 3 整除的数字？

The first line of the input contains a positive integer $s$. The number of digits of the number $s$ is between $1$ and $2\cdot10^5$, inclusive. The first (leftmost) digit is not equal to 0.

输入的第一行包含一个正整数 $s$。数字 $s$ 的位数在 $1$ 到 $2\cdot10^5$ 之间（含端点）。第一位（最左侧）数字不等于 $0$。

Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$.

输出 Polycarp 通过对给定数字 $s$ 进行竖直切割所能得到的、能被 $3$ 整除的数字的最大个数。

In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $3$.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $33$ digits 0. Each of the $33$ digits 0 forms a number that is divisible by $3$.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$, $9$, $201$ and $81$ are divisible by $3$.

在第一个例子中，对数字进行最优分割的一种方案是：3|1|21。

在第二个例子中，无需进行任何分割。给定的数字 6 本身构成一个能被 $3$ 整除的数。

在第三个例子中，必须在每两个相邻数字之间都进行分割。结果，Polycarp 得到一个数字 1 和 33 个数字 0。这 33 个数字 0 中的每一个都单独构成一个能被 $3$ 整除的数。

在第四个例子中，一种最优分割方案是：2|0|1|9|201|81。其中，数字 $0$、$9$、$201$ 和 $81$ 均能被 $3$ 整除。