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.

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 a line with an integer representing the number of substhreengs contained in $S$.

Input

130a303

Output

9

Input

0000000000

Output

55

Input

icpc2014regional

Output

2