Polycarp and Div 3

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp likes numbers that are divisible by 3.

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

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

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 $\mathrm{33 that\; Polycarp\; can\; obtain?}$

Input

The first line of the input contains a positive integer $\mathrm{ss.\; The\; number\; of\; digits\; of\; the\; number ss is\; between 11 and 2\cdot 1052\cdot 105,\; inclusive.\; The\; first\; (leftmost)\; digit\; is\; not\; equal\; to 0.}$

Output

Print the maximum number of numbers divisible by $\mathrm{33 that\; Polycarp\; can\; get\; by\; making\; vertical\; cuts\; in\; the\; given\; number ss.}$

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

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

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $\mathrm{00, 99, 201201 and 8181 are\; divisible\; by 33.}$

 

题意：给我们一个数，我们可以对这个数进行任意的划分，但是不能出现前缀零的无意义数，问我们最多可以划分出几个可以整除三的数？

分析：直接遍历，考虑这四种情况就可以

1.如果单独的数能整除三，那么这数肯定可以，结果直接加一

2.如果不能整除三，那么将得到一个余数，然后接下来我们会在这个数的基础上加上新的数，如果余数和这个数的余数相同，则中间肯定加了一个能整除三的数，结果加一

3.如果不能整除三的数加上一个数后能整除三，则结果加一

4.如果不能整除三的数加上一个数既不能整除三且余数和之前不相同，则再加一个数肯定会得到和前面两个数相同的余数或者整除三

根据以上分析我们每次加数时将余数打上标志，然后根据上诉分析判断结果是否能加一，记得结果加一后要把标志置为0

 

#include