2812. Eleven Lover

单点时限: 2.0 sec

内存限制: 256 MB

Edward Leven loves multiples of eleven very much. When he sees a number, he always tries to find consecutive subsequences (or substrings) forming multiples of eleven. He calls such subsequences as 11-sequences. For example, he can find an 11-sequence 781 in a number 17819. He thinks a number which has many 11-sequences is a good number. He would like to find out a very good number. As the first step, he wants an easy way to count how many 11-sequences are there in a given number. Even for him, counting them from a big number is not easy.

Fortunately, one of his friends, you, is a brilliant programmer. He asks you to write a program to count the number of 11-sequences. Note that an 11-sequence must be a positive number without leading zeros.

输入格式

The input is a sequence of lines each of which contains a number consisting of less than or equal to $80000$ digits.

The end of the input is indicated by a line containing a single zero, which should not be processed.

输出格式

For each input number, output a line containing the number of 11-sequences.

You can assume the answer fits in a 32-bit signed integer.

样例

Input
17819
1111
11011
1234567891011121314151617181920
0
Output
1
4
4
38

32 人解决,51 人已尝试。

37 份提交通过,共有 114 份提交。

4.9 EMB 奖励。

创建: 10 年,8 月前.

修改: 3 年,4 月前.

最后提交: 1 月,3 周前.

来源: Japan

题目标签