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
# n = int(input())
nums = input()

# Initialize the count of numbers divisible by 3, modulo counts, and total sum
count = 0
mod_counts = [0] * 3
total_sum = 0

for num in nums:
    num = int(num)
    total_sum += num
    remainder = num % 3

    # Increment the count of numbers divisible by 3
    if num == 0:
        count += 1
    elif remainder == 1:
        mod_counts[1] += 1
    elif remainder == 2:
        mod_counts[2] += 1

# Calculate the number of operations needed
operations = 0

# Case 1: Numbers with remainder 1 and remainder 2 exist
if mod_counts[1] != 0 and mod_counts[2] != 0:
    operations = min(mod_counts[1], mod_counts[2]) + count + (max(mod_counts[1], mod_counts[2]) - min(mod_counts[1], mod_counts[2])) // 3

# Case 2: Numbers with only remainder 1 exist
elif mod_counts[1] != 0:
    operations = count + mod_counts[1] // 3

# Case 3: Numbers with only remainder 2 exist
elif mod_counts[2] != 0:
    operations = count + mod_counts[2] // 3

# Case 4: Only numbers divisible by 3 exist
else:
    operations = count

print(operations)
This code reads the i