Поликарп очень любит числа, которые делятся на \(3\).
У него есть длинное число \(s\). Поликарп хочет вырезать из него наибольшее количество чисел, которые делятся на \(3\). Для этого он проводит произвольное количество вертикальных разрезов между парами соседних цифр. В результате, после проведения \(m\) разрезов получается \(m+1\) число. Каждое из полученных чисел Поликарп анализирует и подсчитывает количество тех, которые делятся на \(3\).
Например, если исходное число \(s=3121\), то Поликарп может разрезать его на три части двумя разрезами \(3|1|21\). В результате он получит два числа, которые делятся на \(3\).
Поликарп может провести произвольное количество разрезов, каждый разрез проводится между парой соседних цифр. Числа, которые получатся в итоге не могут содержать лишних лидирующих нулей (то есть число может начинаться с 0 тогда и только тогда, когда это число в точности один символ '0'). Например, 007, 01 и 00099 не являются корректными числами, а 90, 0 и 10001 — являются.
Какое наибольшее количество делящихся на три чисел он сможет получить?
Выходные данные
Выведите наибольшее количество делящихся на \(3\) чисел, которые Поликарп сможет получить, проведя вертикальные разрезы в заданном числе \(s\).
Примечание
Пример оптимального разделения числа для первого теста — 3|1|21.
Во втором тесте никаких разрезов совершать не нужно. Заданное число 6 образует одно число, делящееся на \(3\).
В третьем тесте надо провести разрезы между каждой парой цифр. В результате получим одну цифру 1 и \(33\) цифры 0. Каждая из \(33\) цифр 0 образует число, которое делится на \(3\).
Пример оптимального разделения числа для четвертого теста — 2|0|1|9|201|81. Числа \(0\), \(9\), \(201\) и \(81\) делятся на \(3\).