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).
//package com.company;
// Always comment out package when submitting.

import java.io.*;
import java.util.*;

public class Main {
    public static class Task{
        public int encode(int lastDigit, int rank) {
            return lastDigit * 11 + rank;
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            int[] rankMap = new int[]{-1, 10, 0, 2, 5, 9, 3, 9, 5, 2, 0};
            int[][] map = new int[110][110];
            for (int i = 0; i < 10; i++) {
                for (int j = 1; j < 11; j++) {
                    for (int k = 0; k < j; k++) {
                        map[encode(i, j)][encode(k, rankMap[j])] = 1;
                    }
                }
            }
            char[] arr = sc.next().toCharArray();
            int[] rr = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                rr[i] = arr[i] - '0';
            }
            long[] count = new long[11];
            if (rr[0] != 0)
                count[rr[0]] = 1;
            long tot = 0;
            for (int i = 0; i < rr.length - 1; i++) {
                int next = rr[i + 1];
                long[] nextCount = new long[11];
                if (next != 0)
                    nextCount[next] = 1;
                for (int j = 0; j < 11; j++) {
                    tot += count[j];
                }
//                pw.println(tot);
                for (int j = next + 1; j < 11; j++) {
                    nextCount[(rankMap[j] + next) % 11] += count[j];
                }
                count = nextCount;
            }
            for (int i = 1; i < 11; i++) {
                tot += count[i];
            }
            pw.println(tot);


//            List<Integer> numbers = new ArrayList<>();
//            for (int i = 1; i < 10; i++) {
//                numbers.add(i);
//            }
//            PriorityQueue<Integer> pq = new PriorityQueue<>();
//            int idx = 0;
//            while (idx < 200000) {
//                int tenX = numbers.get(idx) * 10;
//                int remainder = (idx + 1) % 11;
//                for (int i = 0; i < remainder; i++) {
//                    pq.add(tenX + i);
//                }
//                idx++;
//                if (idx == numbers.size()) {
//                    numbers.add(pq.poll());
//                }
//            }
//            Map<Integer, Integer> numberRank = new HashMap<>();
//            for (int i = 0; i < 200; i++) {
//                numberRank.put(numbers.get(i), i + 1);
//            }
//            pw.println(numberRank.get(80) % 11);
//            pw.println(numberRank.containsKey(8028));
//            pw.println(numberRank.containsKey(282));
//            for (Map.Entry<Integer, Integer> en : numberRank.entrySet()) {
//                int number = en.getKey();
//                int val = en.getValue();
//                if (numberRank.containsKey(10 * number)) {
//                    pw.println((val % 11) + " " + (numberRank.get(number * 10) % 11));
//                    if (numberRank.get(number * 10) % 11 != rankMap[val % 11]) {
//                        throw new RuntimeException();
//                    }
//                }
//            }
        }
    }

    // template, actual code is in class Task.
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
//        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    // Faster IO with BufferedReader wrapped with Scanner
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}