Chef Ciel likes 8. Ciel's restaurant has many menus whose prices are multiples of 8. Now, Ciel 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 Ciel 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.