p01300 Eleven Lover
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.



Input

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.

Output

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.

Example

Input

17819
1111
11011
1234567891011121314151617181920
0


Output

1
4
4
38
```python
while(True):
    s = input()
    m = len(s)
    if s == "0":
        quit()
    dp = [[0 for j in range(11)] for i in range(m)]
    for i in range(m):
        n = int(s[i])
        if n == 0:
            tmp = dp[i-1][1:]
            tmp.reverse()
            dp[i] = [dp[i-1][0]]+tmp
        else:
            tmp = dp[i-1][1:]
            tmp.reverse()
            tmp = [dp[i-1][0]]+tmp
            dp[i] = tmp[-n:]+tmp[:-n]
            dp[i][n] += 1
    ans = 0
    for i in range(m):
        ans += dp[i][0]
    print(ans)


```