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?


-----Input-----

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.


-----Output-----

Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$.


-----Examples-----
Input
3121

Output
2

Input
6

Output
1

Input
1000000000000000000000000000000000

Output
33

Input
201920181

Output
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 $3$.

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

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$, $9$, $201$ and $81$ are divisible by $3$.

Difficulty: introductory

Starter code:

Solutions:
n=input()
ls=''
t=0
for i in range(len(n)):
    if int(n[i])%3==0:
        ls=''
        t+=1
    else:
        ls+=n[i]
        for j in range(0,len(ls)):
            if int(ls[j:])%3==0:
                t+=1
                ls=''
                break
print(t)
    



'''
////////////////      //////        ///////      //             ///////     //  //   //
////          //    ///   ///     ///    ///     //            ///  ///     ////     //
////    ////       ///     ///   ///      ///    //           /////////     ////     ///////
////     /////    ///       /// ///        ///   //          ///    ///     ////     //   //
//////////////     ///////////   ///////////     //////     ///     ///     //  //   //   //
'''



res_plain = 0
res_1 = -200000
res_2 = -200000
s = input()
for c in s:
	if c in '147':
		res_plain, res_1, res_2 = res_2, res_plain, res_1
	elif c in '258':
		res_plain, res_1, res_2 = res_1, res_2, res_plain
	res_plain = max(res_1, res_2, res_plain+1)
print(res_plain)


n = list(input())
cntr = 0
marks = []
for i in range(len(n)):
    marks.append(0)
for i in range(len(n)):
    if int(n[i]) % 3 == 0:
        #print(i, cntr, marks)
        cntr += 1
        marks[i] = 1
    elif marks[i] == 0:
        marks[i] = 1
        tmpcnt = int(n[i])
        mrk = -1
        for j in range(2):
            if i + j + 1 < len(n):
                if (int(n[i+j+1])% 3 != 0):
                    if (tmpcnt + int(n[i+j+1]) )%3 == 0:
                        cntr += 1
                        mrk = i+j+1
                       # print(i, cntr, marks)
                        break
                    else:
                        tmpcnt += int(n[i+j+1])
                else:
                    break
        if mrk != -1:
            for k in range(i + 1, mrk + 1):
          #      print(i,k)
                marks[k] = 1
print(cntr)


def main():
    ret = 0
    lst = [int(i) for i in input()]
    l = len(lst)
    ind = 0
    while ind < l:
        if lst[ind] % 3 == 0:
            ind += 1
            ret += 1
        elif l - ind >= 2 and ((lst[ind] + lst[ind + 1]) % 3 == 0 or lst[ind + 1] % 3 == 0):
            ret += 1
            ind += 2
        elif l - ind >= 3  and ((lst[ind] + lst[ind + 1] + lst[ind + 2]) % 3 == 0 or(lst[ind + 1] + lst[ind + 2]) % 3 == 0 or lst[ind + 2] % 3 == 0):
            ret += 1
            ind += 3
        else: break
    print(ret)
    return 0
main()

s = str(input())

prev_sum = 0

ans = 0
f_el = 0
need = True
for el in s:
    el  = int(el)

    if el % 3 == 0:
        ans += 1
        prev_sum = 0
        need = True
        continue

    if need:
        f_el = el
        need = False
        prev_sum = el
        continue
    
    prev_sum += el
    
    if  prev_sum % 3 ==  0 or (prev_sum - f_el) % 3 == 0:
        ans += 1
        prev_sum = 0
        need = True
    

print(ans)


s = input()
ost = []
for i in map(int,s):
    ost += [i%3]
now = 0
last = -1
answer = 0
for i in ost:
    if i == 0:
        now = []
        answer += 1
    else:
        if now == 2:
            now = 0
            answer += 1
        elif now == 1:
            if last != i:
                answer += 1
                now = 0
            else:
                now = 2
        else:
            now = 1
            last = i
print(answer)

T = input()
n = len(T)
i = 0
L = []
t = 0
while i < n:
    if int(T[i]) % 3 == 0:
        t+=1
        L=[]
    else:
        L.append(int(T[i]) % 3)
        if L == [1,1,2] or L == [1,1,1] or L == [1,2] or L == [2,1] or L == [2,2,1] or L == [2,2,2]:
            L=[]
            t+=1
    i+=1
print(t)


s = [int(x) % 3 for x in input()]

i = 0
ans = 0
n = len(s)

while i < n:
	if s[i] == 0:
		ans += 1
		i += 1
		continue
	if s[i] == 1:
		if i + 1 < n and s[i + 1] == 2:
			ans += 1
			i += 2
			continue
		if i + 2 < n and s[i + 1] == s[i + 2] == 1:
			ans += 1
			i += 3
			continue
	if s[i] == 2:
		if i + 1 < n and s[i + 1] == 1:
			ans += 1
			i += 2
			continue
		if i + 2 < n and s[i + 1] == s[i + 2] == 2:
			ans += 1
			i += 3
			continue
	i += 1
print(ans)

s = [int(i) for i in input()]

count = 0
current = []
for h, i in enumerate(s):
    for j in range(len(current)):
        current[j] = current[j] * 10 + i
    current.append(i)
    if h + 1 < len(s) and s[h + 1] != 0:
        for m in current:
            if m % 3 == 0:
                count += 1
                current = []
                break
    else:
        for m in current:
            if m % 3 == 0:
                count += 1
                current = []
                break
print(count)


import sys

def main():
    s = input()
    n = len(s)
    
    lim = 243
    ar = [int(c) for c in s]
    
    dp = [0] * (n + lim + 3)
    for i in range(n - 1, -1, -1):
        x = 0
        k = 1 if ar[i] == 0 else lim
        
        for j in range(k):
            if (i + j) == n:
                break
            
            x = ((x * 10) + ar[i + j]) % 3
            dp[i] = max(dp[i], dp[i + j + 1] + (x == 0))
    
    print(dp[0])

def __starting_point():
    main()

__starting_point()

ls = [int(i) % 3 for i in input()]

ls.reverse()

cnt = 0

lst = 0
sub = 0
for i in ls:
    if i == 0 or lst + i == 3 or sub + i == 3:
        sub = 0
        lst = 0
        cnt += 1
    else:
        lst = (lst + i) % 3
        sub = i

print(cnt)

ls = [int(i) % 3 for i in input()]

ls.reverse()

cnt = 0

t = 0
s = 0
for j, i in enumerate(ls):
    if i == 0 or t + i == 3 or s + i == 3:
        s = 0
        t = 0
        cnt += 1
    else:
        t = (t + i) % 3
        s = i

print(cnt)

s = list(map(int, input()))
cur = len(s) - 1
x = True
tmp = 0
ans = 0

while cur >= 0:
    tmp += s[cur] * x
    x *= 10

    if s[cur] == 0:
        ans += 1
        tmp = 0
        x = 1
    else:
        tmp2 = tmp
        # print(tmp2)
        while tmp2 != 0:
            if tmp2 % 3 == 0:
                ans += 1
                tmp = 0
                x = 1
                break
            tmp2 //= 10
        
    cur -= 1

print(ans)

a = list(map(int, list(input())))

if a[0] % 3 == 0:
    cnt = 1
    last_free = 1
else:
    cnt = 0
    last_free = 0

for i in range(1, len(a)):
    if (a[i] % 3 == 0):
        cnt += 1
        last_free = i + 1
    else:
        sm = 0
        # print(i)
        for j in range(i, last_free - 1, -1):
            sm += a[j]
            # print(j, end=", ")
            if sm % 3 == 0:
                #print("GOT")
                cnt += 1
                last_free = i + 1
                break
        #print("")
print(cnt)


s=list(map(int,input()))
ans=0
L=[[]]
for i in s:
    r=i%3
    if r!=0:
        L[-1].append(r)
    else:
        L.append([])
        ans+=1
n=len(L)
for A in L:
    m=len(A)
    k=0
    x=0
    f=[True]*m
    for i in range(m):
        x+=A[i]
        if x%3==0 or (i!=0 and A[i-1]+A[i]==3 and f[i-1]):
            x=0
            f[i]=False
            k+=1
    kk=0
    '''
    x=0
    for i in range(1,m):
        x+=A[i]
        if x%3==0:
            x=0
            kk+=1
    '''
    ans+=max(k,kk)
    
print(ans)


s = input().strip()

have_one = 0
have_two = 0
res = 0

for c in s:
    x = int(c)
    if x % 3 == 1:
        have_one += 1
    elif x % 3 == 2:
        have_two += 1
    else:
        res += 1
        have_one = 0
        have_two = 0

    if have_one == 3 or have_two == 3 or (have_one > 0 and have_two > 0):
        res += 1
        have_one = 0
        have_two = 0

print(res)


s = input()
n = len(s)
ans = 0
i = 0
while i < n:
    if int(s[i]) % 3 == 0:
        ans += 1
        i += 1
        continue
    if i != n - 1 and int(s[i]) % 3 == 1 and int(s[i + 1]) % 3 == 2:
        ans += 1
        i += 2
        continue
    if i != n - 1 and int(s[i]) % 3 == 2 and int(s[i + 1]) % 3 == 1:
        ans += 1
        i += 2
        continue
    if i < n - 2 and int(s[i]) % 3 == int(s[i + 1]) % 3 == int(s[i + 2]) % 3 == 1:
        ans += 1
        i += 3
        continue
    if i < n - 2 and int(s[i]) % 3 == int(s[i + 1]) % 3 == int(s[i + 2]) % 3 == 2:
        ans += 1
        i += 3
        continue
    i += 1

print(ans)


#!/usr/bin/env python3

s = [int(i) for i in input()]
ans = 0
last = 0
def check(x):
    Sum = 0
    while x != 0:
        Sum += x % 10
        x //= 10
        if Sum % 3 == 0:
            return True
    return False

for i in range(len(s)):
    if s[i] % 3 == 0:
        ans += 1
        last = 0
    else:
        last = last * 10 + s[i]
        if check(last):
            ans += 1
            last = 0
print(ans)


s = [int(i) % 3 for i in input()]

prev = 0
twice = 0
count = 0

for i in s:

    if i == 0:
        count += 1
        twice = 0
        prev = 0

    if i == 1:
        if prev == 2 or twice == 1:
            count += 1
            twice = 0
            prev = 0

        elif prev == 0:
            prev = 1
        else:
            twice = 1

    if i == 2:
        if prev == 1 or twice == 1:
            count += 1
            twice = 0
            prev = 0

        elif prev == 0:
            prev = 2
        else:
            twice = 1

print(count)

num = input()

curr = 0
ans = 0

for i in range(len(num)):
    curr += int(num[i])
    if curr%3 == 0:
        ans += 1
        curr = 0
    elif int(num[i])%3 == 0:
        ans += 1
        curr = 0
    elif i<(len(num)-1):
        if (int(num[i])+int(num[i+1]))%3==0:
            curr = int(num[i])
print(ans)


s = input()
a = list()
for item in s:
    ele = int(item)
    a.append(ele)

n = len(s)
for i in range(n):
    a[i] = a[i]%3


one = 0
two = 0
ans = 0

for i in range(n):
    if a[i]==1:
        one+=1
    elif a[i]==2:
        two+=1
    else:
        one = 0
        two = 0
        ans+=1
        continue
    
    if one and two:
        ans+=1
        one = 0
        two = 0
    elif one==3 and two==0:
        ans+=1
        one = 0
        two = 0
    elif two==3 and one==0:
        ans+=1
        one = 0
        two = 0
        
print(ans)

#codeforces_1005D_live
s = input()
ans = 0;
stack = ""
revStack = ""
cursor = 0
for e in s:
	if e == "0":
		ans += 1
		stack = ""
	elif int(e)%3 == 0:
		ans += 1
		stack = ""
	else:
		stack += e
		if (int(stack)%3 == 0):
			ans += 1
			stack = ""
		elif len(stack) > 2:
			cursor = -1
			revStack = ""
			while -cursor < len(stack):
				revStack = stack[cursor] + revStack
				if int(revStack)%3 == 0:
					ans += 1
					stack = ""
print(ans)