Traveling around the world you noticed that many shop owners raise prices to inadequate values if the see you are a foreigner.

You define inadequate numbers as follows: 

  * all integers from 1 to 9 are inadequate; 
  * for an integer x ≥ 10 to be inadequate, it is required that the integer ⌊ x / 10 ⌋ is inadequate, but that's not the only condition. Let's sort all the inadequate integers. Let ⌊ x / 10 ⌋ have number k in this order. Then, the integer x is inadequate only if the last digit of x is strictly less than the reminder of division of k by 11. 



Here ⌊ x / 10 ⌋ denotes x/10 rounded down.

Thus, if x is the m-th in increasing order inadequate number, and m gives the remainder c when divided by 11, then integers 10 ⋅ x + 0, 10 ⋅ x + 1 …, 10 ⋅ x + (c - 1) are inadequate, while integers 10 ⋅ x + c, 10 ⋅ x + (c + 1), …, 10 ⋅ x + 9 are not inadequate.

The first several inadequate integers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32 …. After that, since 4 is the fourth inadequate integer, 40, 41, 42, 43 are inadequate, while 44, 45, 46, …, 49 are not inadequate; since 10 is the 10-th inadequate number, integers 100, 101, 102, …, 109 are all inadequate. And since 20 is the 11-th inadequate number, none of 200, 201, 202, …, 209 is inadequate.

You wrote down all the prices you have seen in a trip. Unfortunately, all integers got concatenated in one large digit string s and you lost the bounds between the neighboring integers. You are now interested in the number of substrings of the resulting string that form an inadequate number. If a substring appears more than once at different positions, all its appearances are counted separately.

Input

The only line contains the string s (1 ≤ |s| ≤ 10^5), consisting only of digits. It is guaranteed that the first digit of s is not zero.

Output

In the only line print the number of substrings of s that form an inadequate number.

Examples

Input


4021


Output


6


Input


110


Output


3

Note

In the first example the inadequate numbers in the string are 1, 2, 4, 21, 40, 402. 

In the second example the inadequate numbers in the string are 1 and 10, and 1 appears twice (on the first and on the second positions).
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from cStringIO import StringIO
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    from io import BytesIO as StringIO


class FastI:
    stream = StringIO()
    newlines = 0

    def readline(self):
        while self.newlines == 0:
            b, ptr = os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell()
            self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr)
            self.newlines += b.count(b'\n') + (not b)

        self.newlines -= 1
        return self.stream.readline()


class FastO(IOBase):
    def __init__(self):
        stream = StringIO()
        self.flush = lambda: os.write(1, stream.getvalue()) and not stream.truncate(0) and stream.seek(0)
        self.write = stream.write if sys.version_info[0] < 3 else lambda b: stream.write(b.encode())


class ostream:
    def __lshift__(self, a):
        if a == endl:
            sys.stdout.write('\n')
            sys.stdout.flush()
        else:
            sys.stdout.write(str(a))
        return self


sys.stdin, sys.stdout = FastI(), FastO()
input, flush = sys.stdin.readline, sys.stdout.flush
cout, endl = ostream(), object()


def main():
    D = map(int, sys.stdin.readline().strip())
    Sum = 0
    c = [0] * 11
    for x in D:
        cn = [0] * 11
        if x != 0:
            cn[x] += 1
        for i in xrange(x + 1, 11):
            cn[((i - 1) * i // 2 + x + 10) % 11] += c[i]
        c = cn
        Sum += sum(c)
    cout << Sum << endl


if __name__ == '__main__':
    main()
