Preparing NOJ

IQ value

2000ms 262144K

Description:

Sdl recently scored in codeforces crazy, but 300iq is the god of codeforces, sdl wants to surpass him, but 300iq is very strong.The reason why he is strong is because of his IQ value is 300, sdl finds that 300 is a multiple of 30, so sdl determines to collect the power of everyone, assuming that everyone's IQ value can be seen as a string, Every character belong to (0-9)How many substrings are multiples of 30?

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.

Input:

The input file contains several blocks of data. For each block, the single line contains a string consisted of characters 0 to 9.

For each block of data: $1 \leq |s| \leq 1 \times 10^5$.

Output:

For each case, output the number of substrings that are multiples of 30 when considered as decimal integers.

Sample Input:

600
30

Sample Output:

5
2

Info

Provider NOJ

Code NOJ2384

Tags

Submitted 87

Passed 24

AC Rate 27.59%

Date 08/15/2019 01:18:45

Related

Nothing Yet