Restaurant Problem

3.1

11 votes
Problem

Kirti likes 8. Kirti's restaurant has many menus whose prices are multiples of 8. Now, Kirti has some digits written on a wooden board, and she'd like to cut the board to display prices in a new menu. In how many ways can Kirti choose consecutive digits from the board which denote integer multiples of 8?

In this problem, an integer must not have leading zeros. For example, 0, 8, 48, 1000 are integer multiples of 8, but 00, 5, 58, 01000 are not.

INPUT

An input contains a string S, which denotes digits written on the wooden board.

OUTPUT

Print the number of ways in which Kirti can choose consecutive digits which denote integer multiples of 8.

CONSTRAINTS

1 ≤ |S| ≤ 1000000 (106), where |S| means the length of S.

S doesn't contain non-digit charactors.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Kirti can choose 5, 8, 5, 8, 58, 85, 58, 585, 858 and 5858. Here, only 8 and 8 are multiples of 8.

Editor Image

?