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
import sys
import threading
input = sys.stdin.readline().rstrip
def main():
    n = list(input())
    memo = {}

    def dp(idx, _sum ):

        if (idx , _sum) in memo:
            return memo[(idx,_sum)]

        if idx ==len(n):
            return 0 
        

        _sum = _sum + int(n[idx])
        ans = 0 
        a , b ,  c = 0 , 0 , 0 
        if _sum % 3 == 0:
            #exclude the number
            a = dp(idx + 1 , 0)
            
        
        else:

            #exclude the number
            b = dp(idx + 1 , 0)
            #include the number 
            c = dp(idx + 1 , _sum)
        
        memo[(idx,_sum)] = max(a,b,c) + int(_sum % 3 == 0)
        return memo[(idx,_sum)]
    






    print(dp(0,0))

if __name__ == '__main__':
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

