Divisible by 3

You will be given a string containing digits. You have to say the number of sub strings whose sum is divisible by 3.

Input

The only line of input containing a string s. (1 ≤ |s| ≤ 106), |s| denotes length of the string.
The characters will be between 0 to 9.

Output

The output will contain the total number of substring sum of which are divisible by 3.

Sample

Input	Output
312012	11