当前没有测试数据。

题目描述

300iq loves numbers who are multiple of 300. One day he got a string consisted of numbers. He wants to know how many substrings in the string are multiples of 300 when considered as decimal integers. Note that leading and trailing zeros are allowed (both in original string and substrings you chose) and the same substring appearing in different places can be counted multiple times.

输入格式

A single line consisting a string consisted of characters '0' to '9'.

输出格式

The number of substrings that are multiples of 300 when considered as decimal integers.

样例

样例输入 1

600

样例输出 1

4

样例输入 2

123000321013200987000789

样例输出 2

55

数据范围与提示

'600', '0', '0', '00' are multiples of 300. (Note that '0' are counted twice because it appeared two times)

let the string in the input be s, 1≤∣s∣≤10^5.