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
s = input()
count = 0
p = [int(s[0])]
m = int(s[0])
def check(n,c):
    ok = False
    for i in range(1,len(n)):
        if ok:
            break
        for j in range(i,len(n)):
            if sum(n[i-1:j+1]) % 3 == 0:
                ok = True
                global p, count
                p = []
                count = c + 1
                break
if s[0] == '3' or s[0] == '6' or s[0] == '9' or s[0] == '0':
    count += 1
    m = 0
    p = []
for i in range(1,len(s)):
    if s[i] == '3' or s[i] == '6' or s[i] == '9' or s[i] == '0':
        count += 1
        m = 0
        p = []
    else:
        m += int(s[i])
        p.append(int(s[i]))
        if m % 3 == 0:
            count += 1
            m = 0
            p = []
        else:
            if len(p) > 1:
                check(p,count)
print(count)

# Thu Sep 30 2021 10:09:26 GMT+0300 (Москва, стандартное время)
