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).
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool smin(T &a, const T &b) {
  return a > b ? a = b : a;
}
template <typename T>
inline bool smax(T &a, const T &b) {
  return a < b ? a = b : a;
}
const int N = (int)12, mod = (int)0;
long long dp[N][N][N], odp[N][N][N];
int nxt_st_sv[N][N][N][N], nxt_pos_sv[N][N][N][N], nxt_num_sv[N][N][N][N];
int main() {
  string s;
  cin >> s;
  int n = (int)s.size();
  long long res = 0;
  for (int cur = 0; cur <= 10; ++cur) {
    for (int st = 0; st <= 10; ++st)
      for (int num = 0; num <= 10; ++num) {
        for (int pos = 0; pos <= 10; ++pos) {
          int nxt_start = (st + num) % 11;
          int nxt_pos = nxt_start;
          for (int c = st; c != pos; c = (c + 1) % 11) {
            nxt_pos += c;
            nxt_pos %= 11;
          }
          nxt_pos = (nxt_pos + cur) % 11;
          int nxt_num = 0;
          for (int c = st, i = 0; i < num; ++i, c = (c + 1) % 11) {
            nxt_num = (nxt_num + c) % 11;
          }
          nxt_st_sv[cur][st][num][pos] = nxt_start;
          nxt_pos_sv[cur][st][num][pos] = nxt_pos;
          nxt_num_sv[cur][st][num][pos] = nxt_num;
        }
      }
  }
  for (int j = 0; j < n; ++j) {
    memcpy(odp, dp, sizeof dp);
    memset(dp, 0, sizeof dp);
    int cur = s[j] - '0';
    if (cur != 0) dp[0][10][cur]++;
    for (int st = 0; st <= 10; ++st)
      for (int num = 0; num <= 10; ++num) {
        for (int pos = cur + 1; pos <= 10; ++pos)
          if (odp[st][num][pos]) {
            int nxt_start = nxt_st_sv[cur][st][num][pos];
            int nxt_pos = nxt_pos_sv[cur][st][num][pos];
            int nxt_num = nxt_num_sv[cur][st][num][pos];
            dp[nxt_start][nxt_num][nxt_pos] += odp[st][num][pos];
          }
      }
    for (int a = 0; a <= 10; ++a)
      for (int b = 0; b <= 10; ++b)
        for (int c = 0; c <= 10; ++c)
          if (dp[a][b][c]) {
            res += dp[a][b][c];
          }
  }
  cout << res << endl;
}
