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?
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.
3121
2
6
1
1000000000000000000000000000000000
33
201920181
4
4
0
10
1
11
0
12
1
13
1
31
1
14139582796
6
1670000
5
604500
5
40041
2
10000170
5
def div3(s):
    c = 0
    for ch in s:
        c += int(ch)
        c = c%3
    if c == 0:
        return True
    return False


s = input()

counter = 0

strings = []
to_keep = []
keep = 0
for i in range(len(s)):
    if s[i] in ('0', '3', '6', '9'):
        if keep != i:
            to_keep.append((keep, i-1))
        counter += 1
        keep = i+1
if keep != i+1:
    to_keep.append((keep, i))

for keeping in to_keep:
    strings.append(s[keeping[0]:keeping[1]+1])

next_strings = []
while True:
    for string in strings:
        if len(string) == 0:
            continue
        if len(string) < 3:
            if div3(string):
                counter += 1
        elif len(string) == 3:
            counter += 1
        elif len(string) == 4:
            if div3(string[0:2]) and div3(string[2:4]):
                counter += 2
            else:
                counter += 1
        elif len(string) == 5:
            if div3(string[0:2]) or div3(string[3:5]):
                counter += 2
            else:
                counter += 1
        else:
            left_cut = 3
            if div3(string[0:2]):
                left_cut = 2
            right_cut = -3
            if div3(string[-2:]):
                right_cut = -2
            counter += 2
            next_strings.append(string[left_cut:right_cut])
    if not next_strings:
        break
print(counter)

# Sat Oct 02 2021 18:30:24 GMT+0300 (Москва, стандартное время)
