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.

17819 1111 11011 1234567891011121314151617181920 0

1 4 4 38

Source: ACM International Collegiate Programming Contest
, ACM-ICPC Japan Alumni Group Practice Contest 2009, 2009-11-01

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/