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


def main():
    s = sys.stdin.readline().rstrip()
    N = len(s)
    B1, B2 = [0] * (N + 10), [0] * (N + 10)

    def add(b, idx, x):
        while idx <= N:
            b[idx] += x
            idx += idx & -idx

    def range_add(l, r, x):
        add(B1, l, x)
        add(B1, r + 1, -x)
        add(B2, l, x * (l - 1))
        add(B2, r + 1, -x * r)

    def sum(b, idx):
        total = 0
        while idx > 0:
            total += b[idx]
            idx -= idx & -idx
        return total

    def prefix_sum(idx):
        return sum(B1, idx) * idx - sum(B2, idx)

    def range_sum(l, r):
        return prefix_sum(r) - prefix_sum(l - 1)

    range_add(1, N, 1)
    pref = [0] * (N + 1)
    for i in range(1, N + 1):
        pref[i] = pref[i - 1] + ord(s[i - 1]) - ord('0')

    ans = 0
    for d in range(1, N + 1):
        for i in range(N):
            if d > 1 and s[i] == '0': continue
            if i + d - 1 < N and range_sum(i + 1, i + d) == d and (pref[i + d] - pref[i]) % 3 == 0:
                ans += 1
                range_add(i + 1, i + d, -1)

    print(ans)


if __name__ == '__main__':
    main()
