Eleven Lover

Time limit8sMemory limit512 MB

Summary

For each number given as a digit string, count its substrings with no leading zero that are divisible by 11.

Level: Medium6 of 10
Topics: Math, Prefix sum, String
Solved: No attempts yet

Problem

Edward Leven loves multiples of eleven. Whenever he sees a number, he looks inside it for a run of consecutive digits that forms a multiple of eleven. He calls such a run an 11-sequence. For example, the number 17819 contains the 11-sequence 781.

Edward thinks a number with many 11-sequences is a good number, and he wants to find a very good number. As a first step he needs an easy way to count how many 11-sequences a given number contains. Counting them by hand in a large number is not easy even for him. Write a program that counts the 11-sequences.

An 11-sequence must be a positive number with no leading zero, so the first digit of the run cannot be 0. Two runs at different start or end positions count separately even when they spell the same value.

Input

The input is a sequence of lines. Each line contains one number with at most 80000 digits.

The end of the input is a line containing a single zero. Do not process that line.

Output

For each input number, print on its own line the number of 11-sequences it contains.

The answer fits in a 32-bit signed integer.

Examples7

Example 1

Input

17819
1111
11011
1234567891011121314151617181920
0

Expected output

Example 2
Input
```
11
0
```
Expected output
```
1
```
Example 3
Input
```
011
0
```
Expected output
```
1
```
Example 4
Input
```
1100
0
```
Expected output
```
3
```
Example 5
Input
```
1234567
0
```
Expected output
```
0
```
Example 6
Input
```
99999999
0
```
Expected output
```
16
```
Example 7
Input
```
5
10
100
1001
0
```
Expected output
```
0
0
0
1
```