#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1.01e9;
const long long infll = (long long)1.01e18;
const long double eps = 1e-9;
const long double pi = acos((long double)-1);
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
const int k = 11;
int go[k][k];
void precalc() {
  int cur = 10;
  for (int r = 0; r < k; r++) {
    for (int i = 0; i < k; i++) {
      go[r][i] = -1;
    }
    for (int d = 0; d < r; d++) {
      go[r][d] = cur;
      cur = (cur + 1) % k;
    }
  }
}
const int maxn = (int)1e5 + 5;
int n;
string s;
char tmp[maxn];
bool read() {
  if (scanf("%s", tmp) < 1) {
    return false;
  }
  s = tmp;
  n = ((int)(s).size());
  return true;
}
int dp[maxn][k];
void solve() {
  for (int i = 0; i < k; i++) {
    dp[n][i] = 0;
  }
  for (int i = n - 1; i >= 0; i--) {
    int d = (s[i] - '0');
    for (int r = 0; r < k; r++) {
      auto &cur = dp[i][r];
      cur = 0;
      if (go[r][d] == -1) {
        continue;
      }
      cur = 1 + dp[i + 1][go[r][d]];
    }
  }
  long long res = 0;
  for (int i = 0; i < n; i++) {
    int d = (s[i] - '0');
    if (!d) {
      continue;
    }
    res += 1 + dp[i + 1][d];
  }
  printf("%lld\n", res);
}
int main() {
  precalc();
  while (read()) {
    solve();
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1.01e9;
const long long infll = (long long)1.01e18;
const long double eps = 1e-9;
const long double pi = acos((long double)-1);
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
const int k = 11;
int go[k][k];
void precalc() {
  int cur = 10;
  for (int r = 0; r < k; r++) {
    for (int i = 0; i < k; i++) {
      go[r][i] = -1;
    }
    for (int d = 0; d < r; d++) {
      go[r][d] = cur;
      cur = (cur + 1) % k;
    }
  }
}
const int maxn = (int)1e5 + 5;
int n;
string s;
char tmp[maxn];
bool read() {
  if (scanf("%s", tmp) < 1) {
    return false;
  }
  s = tmp;
  n = ((int)(s).size());
  return true;
}
int dp[maxn][k];
void solve() {
  for (int i = 0; i < k; i++) {
    dp[n][i] = 0;
  }
  for (int i = n - 1; i >= 0; i--) {
    int d = (s[i] - '0');
    for (int r = 0; r < k; r++) {
      auto &cur = dp[i][r];
      cur = 0;
      if (go[r][d] == -1) {
        continue;
      }
      cur = 1 + dp[i + 1][go[r][d]];
    }
  }
  long long res = 0;
  for (int i = 0; i < n; i++) {
    int d = (s[i] - '0');
    if (!d) {
      continue;
    }
    res += 1 + dp[i + 1][d];
  }
  printf("%lld\n", res);
}
int main() {
  precalc();
  while (read()) {
    solve();
  }
  return 0;
}

```