Count Non-Overlapping "11" Substrings

Background

In a string processing exercise, Congcong encountered an interesting problem that requires him to solve it using recursive thinking.

Problem Description

Given a string, compute recursively (no loops) the number of "11" substrings in the string. The "11" substrings should not overlap.

Input Format

Input is given from standard input in the following format.

A string $S$.

Output Format

Output is printed to standard output in the following format.

An integer representing the number of non-overlapping "11" substrings.

Sample

11abc11

2

abc11x11x11

3

111

1

Sample Explanation

For sample 1 11abc11, the first "11" is at index 0, and the second "11" is at index 5. They are non-overlapping, so the total count is 2. For sample 2 abc11x11x11, there are three non-overlapping "11" substrings, at indices 3, 7, and 10 respectively. For sample 3 111, the first "11" is at index 0. Since substrings cannot overlap, the second '1' cannot form a new "11" with the first '1', so the total count is 1.

Constraints

The length of string $S$ does not exceed $1000$. Time limit: $1$ second per test case. Memory limit: $1024$ KiB per test case.