Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Foreigner

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTraveling 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 \ge 10$$$ to be inadequate, it is required that the integer $$$\lfloor x / 10 \rfloor$$$ is inadequate, but that's not the only condition. Let's sort all the inadequate integers. Let $$$\lfloor x / 10 \rfloor$$$ 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 $$$\lfloor x / 10 \rfloor$$$ 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 \cdot x + 0, 10 \cdot x + 1 \ldots, 10 \cdot x + (c - 1)$$$ are inadequate, while integers $$$10 \cdot x + c, 10 \cdot x + (c + 1), \ldots, 10 \cdot 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 \ldots$$$. After that, since $$$4$$$ is the fourth inadequate integer, $$$40, 41, 42, 43$$$ are inadequate, while $$$44, 45, 46, \ldots, 49$$$ are not inadequate; since $$$10$$$ is the $$$10$$$-th inadequate number, integers $$$100, 101, 102, \ldots, 109$$$ are all inadequate. And since $$$20$$$ is the $$$11$$$-th inadequate number, none of $$$200, 201, 202, \ldots, 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 \le |s| \le 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).

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/24/2021 22:50:14 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|