D. Поликарп и Div 3
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп очень любит числа, которые делятся на $$$3$$$.

У него есть длинное число $$$s$$$. Поликарп хочет вырезать из него наибольшее количество чисел, которые делятся на $$$3$$$. Для этого он проводит произвольное количество вертикальных разрезов между парами соседних цифр. В результате, после проведения $$$m$$$ разрезов получается $$$m+1$$$ число. Каждое из полученных чисел Поликарп анализирует и подсчитывает количество тех, которые делятся на $$$3$$$.

Например, если исходное число $$$s=3121$$$, то Поликарп может разрезать его на три части двумя разрезами $$$3|1|21$$$. В результате он получит два числа, которые делятся на $$$3$$$.

Поликарп может провести произвольное количество разрезов, каждый разрез проводится между парой соседних цифр. Числа, которые получатся в итоге не могут содержать лишних лидирующих нулей (то есть число может начинаться с 0 тогда и только тогда, когда это число в точности один символ '0'). Например, 007, 01 и 00099 не являются корректными числами, а 90, 0 и 10001 — являются.

Какое наибольшее количество делящихся на три чисел он сможет получить?

Входные данные

В первой строке входных данных записано целое положительное число $$$s$$$. Длина числа $$$s$$$ — от $$$1$$$ до $$$2\cdot10^5$$$ цифр. Первая (самая левая) цифра отлична от 0.

Выходные данные

Выведите наибольшее количество делящихся на $$$3$$$ чисел, которые Поликарп сможет получить, проведя вертикальные разрезы в заданном числе $$$s$$$.

Примеры
Входные данные
3121
Выходные данные
2
Входные данные
6
Выходные данные
1
Входные данные
1000000000000000000000000000000000
Выходные данные
33
Входные данные
201920181
Выходные данные
4
Примечание

Пример оптимального разделения числа для первого теста — 3|1|21.

Во втором тесте никаких разрезов совершать не нужно. Заданное число 6 образует одно число, делящееся на $$$3$$$.

В третьем тесте надо провести разрезы между каждой парой цифр. В результате получим одну цифру 1 и $$$33$$$ цифры 0. Каждая из $$$33$$$ цифр 0 образует число, которое делится на $$$3$$$.

Пример оптимального разделения числа для четвертого теста — 2|0|1|9|201|81. Числа $$$0$$$, $$$9$$$, $$$201$$$ и $$$81$$$ делятся на $$$3$$$.