Description

Problem C - Lucky Substrings

HT Chen is happy that you guys have solved the "exquisite substrings" problem! In order to improve your programming ability, here comes the next challenge :

HT's lucky number is 9. For a string s consists of digits ranged from '0' to '9', if s contains at least one digit of lucky number 9, then s is called "lucky string". HT wants to know how lucky he is today. As a kind of divination, HT will randomly write down a list of strings and ask you to calculate the number of "lucky substrings" in each string.

(If naughty HT is very unlucky today, maybe the midterm will become harder than usual.)

Input

There are multiple lines in each testcase. Each line contains a string s_i that HT writes on the paper.

The input file is ended by 'EOF'.

It is guaranteed that :

• At most 10 lines in each testcase.
• testcase #1 : Sample Input
• testcase #2~4 : 1 ≤ | s_i | ≤ 10, at most one "lucky number" appears in each line
• testcase #5~8 : 1 ≤ | s_i | ≤ 100
• testcase #9 : 1 ≤ | s_i | ≤ 5000
• testcase #10 : 1 ≤ | s_i | ≤ 200000

If you can't pass testcase #9 & #10 immediately, try to solve another two problems first. 

Output

For each string s_i, please output a line contains one integer representing the number of "lucky substrings" in s_i.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss