Problem: Toad Rash has a binary string s. A binary string consists only of zeros and ones.

Let n be the length of s.

Rash needs to find the number of such pairs of integers l, r that 1 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ r, and s_x = s_{x+k} = s_{x+2k}.

Find this number of pairs for Rash.

Input

The first line contains the string s (1 ≤ |s| ≤ 300 000), consisting of zeros and ones.

Output

Output one integer: the number of such pairs of integers l, r that 1 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ r, and s_x = s_{x+k} = s_{x+2k}.

Examples

Input


010101


Output


3


Input


11001100


Output


0

Note

In the first example, there are three l, r pairs we need to count: 1, 6; 2, 6; and 1, 5.

In the second example, there are no values x, k for the initial string, so the answer is 0.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Collection;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Asgar Javadov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        char[] s;
        long result = 0L;
        int right;
        int[] r;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            s = in.next().toCharArray();

            boolean allEq = true;
            for (int i = 1; i < s.length; ++i) {
                if (s[i] != s[0]) {
                    allEq = false;
                    break;
                }
            }

            if (allEq) {
                out.println((s.length - 2) * (long) (s.length - 1) / 2);
                return;
            }

            IntList zeros = new IntList(s.length);
            IntList ones = new IntList(s.length);

            for (int i = 0; i < s.length; i++) {
                if (s[i] == '0')
                    zeros.add(i);
                else
                    ones.add(i);
            }

            zeros.sortAndCompressAsUnique();
            ones.sortAndCompressAsUnique();

            r = new int[s.length];
            right = s.length;
            int zeroIndex = 0;
            int oneIndex = 0;
            for (int i = 0; i < s.length; ++i) {
                if (s[i] == '0') {
                    r[i] = solveBit(zeros, zeroIndex, i, '0');
                    zeroIndex++;
                } else {
                    r[i] = solveBit(ones, oneIndex, i, '1');
                    oneIndex++;
                }
            }

            int leftMost = s.length;
            for (int i = s.length - 1; i >= 0; --i) {
                leftMost = Math.min(r[i], leftMost);
                result += (s.length - leftMost);
            }

            out.println(result);
        }

        private int solveBit(IntList zeros, int pos, int start, char ch) {
            for (int i = pos + 1; i < zeros.size(); ++i) {
                int next = zeros.get(i);
                int nn = next + (next - start);
                if (nn < s.length && s[nn] == ch) {
                    return nn;
                }
                if (nn >= s.length) break;
            }
            return s.length;
        }

    }

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream outputStream) {
            super(outputStream);
        }

        public OutputWriter(Writer writer) {
            super(writer);
        }

        public OutputWriter(String filename) throws FileNotFoundException {
            super(filename);
        }

        public void close() {
            super.close();
        }

    }

    static class InputReader extends BufferedReader {
        StringTokenizer tokenizer;

        public InputReader(InputStream inputStream) {
            super(new InputStreamReader(inputStream), 32768);
        }

        public InputReader(String filename) {
            super(new InputStreamReader(Thread.currentThread().getContextClassLoader().getResourceAsStream(filename)));
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(readLine());
                } catch (IOException e) {
                    throw new RuntimeException();
                }
            }
            return tokenizer.nextToken();
        }

    }

    static class IntList implements Iterable<Integer> {
        public static final int INITIAL_CAPACITY = 4;
        private int size;
        private int[] array;

        public IntList() {
            this(INITIAL_CAPACITY);
        }

        public IntList(int initialCapacity) {
            this.array = new int[initialCapacity];
            this.size = 0;
        }

        public IntList(int[] array) {
            this.array = Arrays.copyOf(array, array.length);
            this.size = this.array.length;
        }

        public IntList(Collection<Integer> collection) {
            this.size = collection.size();
            this.array = new int[size];
            int index = 0;
            for (int e : collection) {
                array[index++] = e;
            }
        }

        public void add(int value) {
            if (size == array.length) {
                ensureCapacity();
            }

            this.array[this.size++] = value;
        }

        public int get(int index) {
            if (index < 0 || index >= size)
                throw new IllegalArgumentException("Expected argument in [0, " + size + "), but found " + index);
            return array[index];
        }

        public void sortAndCompressAsUnique() {
            if (size <= 1) return;

            Arrays.sort(array, 0, size);
            int uniqueSize = 1;
            for (int i = 1; i < size; i++) {
                if (array[i] != array[i - 1])
                    uniqueSize++;
            }

            int[] temp = new int[uniqueSize];
            temp[0] = array[0];
            for (int i = 1, j = 1; i < size; i++) {
                if (array[i] != array[i - 1])
                    temp[j++] = array[i];
            }

            array = temp;
            size = uniqueSize;
        }

        public int size() {
            return this.size;
        }

        private void ensureCapacity() {
            if (size < array.length)
                return;
            this.array = Arrays.copyOf(array, array.length << 1);
        }

        public IntList clone() {
            IntList cloned = new IntList(Math.max(1, this.size));
            for (int i = 0; i < size; ++i)
                cloned.add(array[i]);
            return cloned;
        }

        public Iterator<Integer> iterator() {
            return new IntListIterator();
        }

        private class IntListIterator implements Iterator<Integer> {
            private int current;

            public IntListIterator() {
                this.current = 0;
            }

            public boolean hasNext() {
                return this.current < size;
            }

            public Integer next() {
                return array[current++];
            }

        }

    }
}