Problem: 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⋅10^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.

Solution (in PYTHON):

Solution:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    from math import gcd
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    def gcd(x, y):
        """greatest common divisor of x and y"""
        while y:
            x, y = y, x % y
        return x

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def memodict(f):
    """ Memoization decorator for a function taking a single argument. """
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__


def main():
    s = list(map(lambda x: int(x) % 3, list(input())))

    @memodict
    def solve(x):
        if x == 0:
            if s[0] == 0:
                return 1, 0
            else:
                return 0, s[0]

        res, rem = solve(x - 1)
        if s[x] == 0:
            return res + 1, 0

        case = [(res, rem + s[x])]

        if (rem + s[x]) % 3 == 0:
            case.append((res + 1, 0))

        if (x > 1) and ((s[x - 1] + s[x]) % 3 == 0):
            res2, rem2 = solve(x - 2)
            case.append((res2 + 1, 0))

        if (x > 2) and (s[x - 2] == s[x - 1] == s[x]):
            res3, rem3 = solve(x - 3)
            case.append((res3 + 1, 0))

        return max(case)

    for i in range(len(s)):
        solve(i)

    print(solve(len(s) - 1)[0])


if __name__ == '__main__':
    sync_with_stdio(False)
    main()