First character

 D. Polycarp and Div 3

Polycarp likes numbers that are divisible by 3.

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

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

Input

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

Output

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

Examples

input

Copy

3121

output

Copy

2

input

Copy

6

output

Copy

1

input

Copy

1000000000000000000000000000000000

output

Copy

33

input

Copy

201920181

output

Copy

4

Note

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$3$.

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

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