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()

digits = [int(d) for d in str(s)]
digits.sort(reverse=True)  # Sort the digits in descending order for easy removal

ans = 0

# Step 1: Calculate the sum of the digits
digit_sum = sum(digits)

# Step 2: If the sum is divisible by 3, return the number of cuts made plus 1
if digit_sum % 3 == 0:
    print(len(digits) - 1 + 1)
    exit(0)

# Step 3: Remove digits to make the sum divisible by 3
remove_count = 0  # Number of digits removed
while remove_count < len(digits):
    removed = False

    # Step 3a: Find the minimum number of digits that leave a remainder of 1 or 2 when divided by 3
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] % 3 == 1:
            digits.pop(i)
            removed = True
            break
        elif digits[i] % 3 == 2:
            digits.pop(i)
            removed = True
            break

    if not removed:
        break  # No more digits can be removed

    remove_count += 1

    # Step 3d: Recalculate the sum of the remaining digits
    digit_sum = sum(digits)

    # Step 2: If the sum is divisible by 3, return the number of cuts made plus 1
    if digit_sum % 3 == 0:
        ans = len(digits) - 1 + 1

print(ans)