C - Counting substhreengs

Time limit: 3 s
Memory limit: 256 MiB
Languages: C, C++, Java, Pascal, ... (details)

Substrings are strings formed by choosing a subset of contiguous characters from a string. This is well known. A little more obscure is the definition of substhreengs. A substhreeng is a substring which complies to the following additional requirements:

1. It is non-empty, and composed entirely of base $10$ digits.
2. Interpreted in base $10$ (allowing extra leading zeros), the resulting integer is a multiple of $3$.

For instance, the string $\texttt{130a303}$ contains $9$ substhreengs: the substhreeng $\texttt{3}$ three times, the substhreengs $\texttt{30}$ and $\texttt{0}$ twice each, and the substhreengs $\texttt{303}$ and $\texttt{03}$ once each. The substring $\texttt{30a3}$ is not a substhreeng because it is not composed entirely of base $10$ digits, while the substring $\texttt{13}$ is not a substhreeng because $13$ is not a multiple of $3$.

Notice that two substhreengs are considered different if they are different in length or start at a different position, even if the selected characters are the same.

Given a string, you are asked to count the number of substhreengs it contains.

Input

The input consists of a single line that contains a non-empty string $S$ of at most $10^6$ characters. Each character of $S$ is either a digit or a lowercase letter.

Output

Output a line with an integer representing the number of substhreengs contained in $S$.

Sample test(s)

Input
130a303
Output
9
Input
0000000000
Output
55
Input
icpc2014regional
Output
2